Sizə tam ədəddən ibarət [a_1, a_2, \ldots, a_n] massivi verilib. Bir əməliyyatda aşağıdakıları edə bilərsiniz:
2\le i \le n-1 şərtini ödəyən hansısa seçin.
Fərz edək ki, a_i = x. Onda ədədini a_{i-1} və a_{i+1} elementlərinə əlavə edin, a_i elementini isə ilə əvəz edin.
Məsələn, əgər massiv [1, 2, -1, 3] idisə, biz i = 3 seçib əməliyyatı yerinə yetirə və [1, 1, 1, 2] massivini ala bilərik.
Bu əməliyyatı massivə istənilən sayda tətbiq edə bilərsiniz. Neçə müxtəlif massiv ala bilərsiniz? Əgər sonsuz sayda massiv ala bilirsinizsə, çap edin; əks halda isə bu massivlərin sayını 10^9 + 7 moduluna görə çap edin.
İki massiv ən azı bir mövqedə fərqlənirsə, onlar müxtəlif hesab olunur.
Birinci sətirdə bir tam ədəd (3 \le n \le 10^5) — massivin uzunluğu verilir.
İkinci sətirdə tam ədəd a_1, a_2, \ldots, a_n (-10^9 \le a_i \le 10^9) — massivin elementləri verilir.
Əgər sonsuz sayda massiv ala bilirsinizsə, çap edin; əks halda isə bu massivlərin sayını 10^9 + 7 moduluna görə çap edin.
Nümunə 1
Nümunə 2
Nümunə 3
Birinci nümunədə əməliyyatı yalnız i = 2 üçün tətbiq edə bilərik, bu da iki müxtəlif massiv verir: [18, 9, 2021] və [27, -9, 2030].
İkinci nümunədə hansı əməliyyatı tətbiq etsək də, massiv [0, 0, 0, 0, 0] olaraq qalır.