细胞

题目描述:

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

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

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

输入格式:

包含两行，其中：

第一行为一个正整数n，表示细胞密码的长度。

第二行共n个数字，为给定的细胞密码，中间没有空格。

输出格式:

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

样例输入:

样例1：
1
1

样例2：
1
5

样例3：
2
11

样例输出:

样例1：
0

样例2：
3

样例3：
56

提示:

对于5%的数据满足，n ≤ 6；

对于25%的数据满足，n ≤ 25；

对于60%的数据满足，n ≤ 100；

对于70%的数据满足，n ≤ 300；

对于100%的数据满足，n ≤ 1 000。

时间限制: 2000ms
空间限制: 256MB

---

来源: 浙江省选2011day2t1