[ZJOI2011]细胞

时间限制：20s 空间限制：256MB

题目描述

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

5

【样例输入三】

2

11

样例输出

【样例输出一】

0

【样例输出二】

3

【样例输出三】

56

提示

【数据规模】

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

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

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

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

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

题目来源

Day2