Absolutely Inadequate Operations#12850

Absolutely Inadequate Operations

1 second
256 megabytes
Hard

You are given an array of integers [a_1, a_2, \ldots, a_n]. In one operation you can do the following:

For example, if the array was [1, 2, -1, 3], we can choose i = 3, perform the operation, and obtain the array [1, 1, 1, 2].

You can apply this operation to the array any number of times. How many different arrays can you obtain? If you can obtain infinitely many arrays, print ; otherwise print the number of these arrays modulo 10^9 + 7.

Two arrays are considered different if they differ in at least one position.

Input

The first line contains one integer (3 \le n \le 10^5) — the length of the array.

The second line contains integers a_1, a_2, \ldots, a_n (-10^9 \le a_i \le 10^9) — the elements of the array.

Output

If you can obtain infinitely many arrays, print ; otherwise print the number of these arrays modulo 10^9 + 7.

Examples

Example 1

Loading
Loading

Example 2

Loading
Loading

Example 3

Loading
Loading

Note

In the first sample, we can apply the operation only for i = 2, which gives two different arrays: [18, 9, 2021] and [27, -9, 2030].

In the second sample, whichever operation we apply, the array stays equal to [0, 0, 0, 0, 0].