2222年，人类在银河系外的某颗星球上发现了生命，并且携带了一个细胞回到了地球。经过反复研究，人类已经完全掌握了这类细胞的发展规律：

这种细胞最初的形态是“长条形”，一端是头，一端是尾，中间是躯干。细胞内部含有一列密码（你可以认为它是这种细胞的DNA）。密码是一个长度为 $n$ 的数字串，且仅含有1~9这9种数字，沿着细胞的躯干从头到尾排列着。

首先，细胞会经历一次分裂。细胞将沿躯干方向分裂成若干个球体，躯干将退化成丝状物，连接着相邻的球体。在分裂过程中，质量是均匀分布的。换句话说，若分裂成 $k$ 个球体，每个球体的质量为原来的 $1/k$。然而，密码的分布是不确定的。若分割成 $k$ 个球体，密码会被切割成 $k$ 段（每段长度至少为 $1$），并按从头到尾的顺序分布在各个球体中。如图，为其中一种合法的一次分裂：

接下来，细胞会经历二次分裂。对于每个球体，其中会含有一小段密码（注意它是有序的），我们把它看作一个十进制的数 $T$。这个球体会被分割成 $T$ 个小球体，并排成一排，之间用躯干退化成的丝状物相连接，并且质量仍然是均匀分布的，每个小球体的质量都是原球体的 $1/T$。至此，密码已经发挥了它的作用，便消失了。如图，为二次分裂：

最后，细胞会进行变异。相邻小球体之间的丝状物可能会退化掉，这两个小球体便会以相切的方式直接连接。显然，二次分裂后，除两端外的每个小球体都有两段丝状物与其连接（头尾两端的小球体只有一段丝状物与其相连）。对于每个小球体，必须至少退化一段与其相连的丝状物，否则这个结构不稳定，会继续变异。如图，为一种稳定的变异：

现在，我们想知道，对于一个给定密码的细胞，总共有多少种稳定的结构。两种结构被认为相同，当且仅当他们拥有相同个数的小球体，从头到尾每个小球体的质量相同，并且从头到尾每对相邻小球体之间的连接方式相同（都是通过丝状物相连或都是通过相切直接相连）。你只需要回答这个结果 mod $1000000007$ 即可。

输入格式

第一行为一个正整数 $n$，表示细胞密码的长度。 第二行共 $n$ 个数字，为给定的细胞密码，中间没有空格。

输出格式

只包含一个整数，为细胞的种数 mod $1000000007$ 的结果。

样例数据

样例 1 输入

1
1

样例 1 输出

0

样例 2 输入

1
5

样例 2 输出

3

样例 3 输入

2
11

样例 3 输出

56

数据范围与提示

对于 $5\%$ 的数据满足，$n \leq 6$；

对于 $25\%$ 的数据满足，$n \leq 25$；

对于 $60\%$ 的数据满足，$n \leq 100$；

对于 $70\%$ 的数据满足，$n \leq 300$；

对于 $100\%$ 的数据满足，$n \leq 1\,000$。