1100 : Spanning Trees

Description

Bobo has a string s₁…s_n consisting of zeros and ones, and he constructs an undirected graph G with n vertices v₁, …, v_n. In the graph G, an edge between the vertices v_i and v_j if and only if i < j and s_j = 1.

Find the number of spanning trees of the graph G modulo (10⁹ + 7).

Input

The input consists of several test cases terminated by end-of-file.

The first line of each test case contains an integer n, and the second line contains a string s₁…s_n.

• 1 ≤ n ≤ 10⁵
• s_i ∈ {0, 1}
• s_n − 1 = 1
• The sum of n does not exceed 10⁶.

Output

For each test case, print an integer which denotes the result.

Sample

3
001
4
0101
5
11111

1
3
125

Hint

Source

Author

ftiasch