Bobo has a string $s_1 \dots s_n$ consisting of zeros and ones, and he constructs an undirected graph $G$ with $n$ vertices $v_1, \dots, 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^9 + 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_1 \dots s_n$.
- $1 \leq n \leq 10^5$
- $s_i \in \{0, 1\}$
- $s_{n - 1} = 1$
- The sum of $n$ does not exceed $10^6$.
Output
For each test case, print an integer which denotes the result.
Sample Input
3 001 4 0101 5 11111
Sample Output
1 3 125