Size tam sayıdan oluşan bir [a_1, a_2, \ldots, a_n] dizisi veriliyor. Bir işlemde aşağıdakileri yapabilirsiniz:
2\le i \le n-1 olacak şekilde bir seçin.
a_i = x olsun. Ardından değerini a_{i-1} ve a_{i+1} elemanlarına ekleyin ve a_i elemanını ile değiştirin.
Örneğin, dizi [1, 2, -1, 3] ise i = 3 seçip işlemi uygulayarak [1, 1, 1, 2] dizisini elde edebiliriz.
Bu işlemi diziye istediğiniz kadar uygulayabilirsiniz. Kaç farklı dizi elde edebilirsiniz? Sonsuz sayıda dizi elde edebiliyorsanız yazdırın; aksi takdirde bu dizilerin sayısını 10^9 + 7 moduna göre yazdırın.
İki dizi en az bir konumda farklıysa farklı kabul edilir.
İlk satırda dizinin uzunluğu olan bir tam sayı (3 \le n \le 10^5) — verilir.
İkinci satırda dizinin elemanları olan tam sayı a_1, a_2, \ldots, a_n (-10^9 \le a_i \le 10^9) — verilir.
Sonsuz sayıda dizi elde edebiliyorsanız yazdırın; aksi takdirde bu dizilerin sayısını 10^9 + 7 moduna göre yazdırın.
Örnek 1
Örnek 2
Örnek 3
Birinci örnekte işlemi yalnızca i = 2 için uygulayabiliriz; bu da iki farklı dizi verir: [18, 9, 2021] ve [27, -9, 2030].
İkinci örnekte hangi işlemi uygularsak uygulayalım, dizi [0, 0, 0, 0, 0] olarak kalır.