题目描述
Ene 喜欢回文。
Ene 现在有一些单词。她想选出若干个单词并将它们首尾相连,形成长度恰好为 L 的回文串。每个单词都可以选择多次,也可以不选。
Ene 想知道这样做的方案数。Ene 认为两个方案不同,当且仅当各单词出现次数不同或它们的排列顺序不同,注意多种不同的方案可能会得到同一个回文串。由于答案可能会很大,你需要将答案对 1,000,000,007 取模。
输入格式
从标准输入读入数据。
输入的第一行包含两个正整数 N,L,分别表示单词的数量和需要组成的回文串的长度。保证 1≤N≤333,1≤L≤1000。
接下来 N 行,每行输入一个字符串 si,表示一个单词。保证 1≤|si|≤L,∑Ni=1|si|≤600;输入的单词仅包含小写字符,且互不相同。
输出格式
输出到标准输出。
输出一个非负整数,表示组成回文串的方案数对 1,000,000,007 取模后的结果。
样例
输入
7 9
cats
eel
eve
evil
lee
olive
stack
输出
5
解释
有以下五种方案:
stack
cats
evil
olive
eel
eve
lee
lee
eve
eel
eve
eve
eve
样例
输入
2 2
a
aa
输出
2
解释
有以下两种方案:
a
a
aa
样例
输入
6 12
aa
aab
no
on
pets
step
输出
43