UVa 1401

Remember the Word

from Chapter 3. Data Structures :: String Algorithms :: Examples

Description

Neal是一个对组合问题非常着迷的人，现在他想出了一个关于单词的问题，并将问题丢给Jiejie去考虑。

因为Jiejie记不住数字，所以他只好用树枝来帮助他记忆。限制Jiejie只能使用20071027根树枝，所以他只会记录一个数对20071027取余后的结果。

他要解决的问题是这样的：一个字符串可以通过多种方式被分解成一些小的事先给好的单词。现在给出一个字符串，和若干的单词，Jiejie应该计算出将字符串分解成单词的方式有多少种。

Input

输入文件包括多组样例，对于每组样例：第一行包含一个长度不超过300 000的字符串，第二行包含一个整数 S ，1 ≤ S ≤ 4000。

Output

Solution