题号：NC214402
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
Special Judge, 64bit IO Format: %lld
题目描述
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 (109 + 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 ≤ 105
· si ∈ {0, 1}
· sn-1 = 1
· The sum of n does not exceed 106
输出描述:
For each test case, print an integer which denotes the result.