/ OK / 题库 /

积木塔(tower)

积木塔(tower)

描述

卡尔梦想建一座漂亮的积木塔。今天他的机会终于来了,老板给他了一次建塔的机会。每次他可以从传送带上取一段连续的积木,并依次把它们垒起来(注意先取的放在下面,同一次取的积木,在传送带上靠前的,要放在传送带上靠后的积木的下面)由于是从传送带上取积木,所以他不能返回去取前面的积木(比如:他上一次取了传送带上的第6块积木,无论第3块积木有没有取,他下一次都不能取第3块积木了。老板为了考一考卡尔,规定他必须恰好取K次,且每次都要取积木。给定传送带上的积木和梦想之塔的形状,请计算卡尔有多少种方法建成他的梦想之塔。由于方案可能很多,请你输出方案对123456789117的余数。

输入

多组数据,第一行一个数T(T<=5),表示数据的组数。
每组数据格式如下:
第一行一个数字字符串,表示传送带上的积木。
第二行一个数字K,表示恰好取K次。
第三行一个数字字符串,依次表示梦想之塔从下到上的形状。

输出:

每组数据一行一个数,表示方案总数对123456789117的余数。

样例:

输入:

1
12331123
2
123

输出:

8
样例的方法有 1 23 31123 、 12 3 31123、 123 31123、 12 33112 3 、 12331 123 、1 23311 23 12331 1 23、12331 12 3 共8种
30%的数据 第一个串的长度小于15;
70%的数据 第一个串的长度小于100;
100%的数据 第一个串的长度小于150; K小于第一个串的长度,第二个串的长度小于等于第一个串的长度。

信息

难度
8
分类
(无)
标签
(无)
递交数
32
已通过
3
通过率
9%
上传者