题目描述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

出题Author

ftiasch

来源Source