4439: Spanning Trees

Bobo has a string s1…sn consisting of zeros and ones, and he constructs an undirected graph G with n vertices v1, …, vn. In the graph G, an edge between the vertices vi and vj if and only if i < j and sj = 1.

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

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 s1…sn.

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

3
001
4
0101
5
11111

1
3
125