Se te da un arreglo de números enteros [a_1, a_2, \ldots, a_n]. En una operación puedes hacer lo siguiente:
Elegir algún con 2\le i \le n-1.
Sea a_i = x. Entonces suma a a_{i-1} y a a_{i+1}, y reemplaza a_i por .
Por ejemplo, si el arreglo era [1, 2, -1, 3], podemos elegir i = 3, realizar la operación y obtener el arreglo [1, 1, 1, 2].
Puedes aplicar esta operación al arreglo cualquier cantidad de veces. ¿Cuántos arreglos diferentes puedes obtener? Si puedes obtener una cantidad infinita de arreglos, imprime ; en caso contrario, imprime la cantidad de estos arreglos módulo 10^9 + 7.
Dos arreglos se consideran diferentes si difieren en al menos una posición.
La primera línea contiene un entero (3 \le n \le 10^5) — la longitud del arreglo.
La segunda línea contiene enteros a_1, a_2, \ldots, a_n (-10^9 \le a_i \le 10^9) — los elementos del arreglo.
Si puedes obtener una cantidad infinita de arreglos, imprime ; en caso contrario, imprime la cantidad de estos arreglos módulo 10^9 + 7.
Ejemplo 1
Ejemplo 2
Ejemplo 3
En el primer ejemplo, solo podemos aplicar la operación para i = 2, lo que da dos arreglos diferentes: [18, 9, 2021] y [27, -9, 2030].
En el segundo ejemplo, sin importar qué operación apliquemos, el arreglo sigue siendo igual a [0, 0, 0, 0, 0].