Bobo 有一个由 0 和 1 组成的字符串 $s_1 \dots s_n$，他构建了一个包含 $n$ 个顶点 $v_1, \dots, v_n$ 的无向图 $G$。在图 $G$ 中，顶点 $v_i$ 和 $v_j$ 之间存在边，当且仅当 $i < j$ 且 $s_j = 1$。
求图 $G$ 的生成树数量，结果对 $(10^9 + 7)$ 取模。
输入格式
输入包含多组测试数据，以文件结束符（EOF）结束。
每个测试数据的第一行包含一个整数 $n$，第二行包含一个字符串 $s_1 \dots s_n$。
- $1 \leq n \leq 10^5$
- $s_i \in \{0, 1\}$
- $s_{n - 1} = 1$
- 所有测试数据的 $n$ 之和不超过 $10^6$。
输出格式
对于每组测试数据，输出一个整数，表示结果。
样例
样例输入 1
3 001 4 0101 5 11111
样例输出 1
1 3 125