描述

卡尔梦想建一座漂亮的积木塔。今天他的机会终于来了，老板给他了一次建塔的机会。每次他可以从传送带上取一段连续的积木，并依次把它们垒起来（注意先取的放在下面，同一次取的积木，在传送带上靠前的，要放在传送带上靠后的积木的下面）由于是从传送带上取积木，所以他不能返回去取前面的积木（比如：他上一次取了传送带上的第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小于第一个串的长度，第二个串的长度小于等于第一个串的长度。