题目描述(ID:12235)
标题: 剪气球串
标签: 动态规划
详情:
小明买了一些彩色的气球用绳子串在一条线上,想要装饰房间,每个气球都染上了一种颜色,每个气球的形状都是各不相同的。我们用1到9一共9个数字表示不同的颜色,如12345则表示一串5个颜色各不相同的气球串。但小明希望得到不出现重复颜色的气球串,那么现在小明需要将这个气球串剪成多个较短的气球串,小明一共有多少种剪法?如原气球串12345的一种是剪法是剪成12和345两个气球串。
注意每种剪法需满足最后的子串中气球颜色各不相同(如果满足该条件,允许不剪,即保留原串)。两种剪法不同当且仅当存在一个位置,在一种剪法里剪开了,而在另一种中没剪开。详见样例分析。
输入格式:
第一行输入一个正整数 n(n∈[1,100000] ),表示气球的数量。
第二行输入n个整数a1,a2,..an,ai表示该气球串上第o个气球的颜色。对于任意i ,有 ai∈[1.,9]。
输出格式:
输出一行,第一行输出一个整数,表示满足要求的剪法,输出最终结果除以1000000007后的余数。
样例:

输入

3
1 2 3

输出

4

解释

第一个例子里,我们有以下4种剪法,*表示在这个位置剪,没有*则表示不剪:
1*2*3
1*23
12*3
123

输入

3
1 2 1

输出

3

解释

第二个例子里,我们有以下3种剪法:
1*2*1
1*21
12*1
注意如果不剪的话,原串中包含两个1号颜色的气球,因此不剪是不合法的。一共3种剪法。

输入

7
1 2 3 5 7 2 5

输出

54
登录并解答