勿蹖宠物 - Problem

#7994. 勿蹖宠物

Statistics

题目描述

Ene 喜欢回文。

Ene 现在有一些单词。她想选出若干个单词并将它们首尾相连，形成长度恰好为 $L$ 的回文串。每个单词都可以选择多次，也可以不选。

Ene 想知道这样做的方案数。Ene 认为两个方案不同，当且仅当各单词出现次数不同或它们的排列顺序不同，注意多种不同的方案可能会得到同一个回文串。由于答案可能会很大，你需要将答案对 $1,000,000,007$ 取模。

输入格式

从标准输入读入数据。

输入的第一行包含两个正整数 $N, L$，分别表示单词的数量和需要组成的回文串的长度。保证 $1\le N\le 333$，$1\le L\le 1000$。

接下来 $N$ 行，每行输入一个字符串 $s_i$，表示一个单词。保证 $1\le |s_i| \le L$，$\sum_{i=1}^N |s_i| \le 600$；输入的单词仅包含小写字符，且互不相同。

输出格式

输出到标准输出。

输出一个非负整数，表示组成回文串的方案数对 $1,000,000,007$ 取模后的结果。

样例

输入

7 9
cats
eel
eve
evil
lee
olive
stack

输出

解释

有以下五种方案：

stack cats
evil olive
eel eve lee
lee eve eel
eve eve eve

样例

输入

2 2
a
aa

输出

解释

有以下两种方案：

a a
aa

样例

输入

6 12
aa
aab
no
on
pets
step

输出

About Issues

We understand that our problem archive is not perfect. If you find any issues with the problem, including the statement, scoring configuration, time/memory limits, test cases, etc.

You may use this form to submit an issue regarding the problem. A problem moderator will review your issue and proceed it properly.

STOP! Before you submit an issue, please READ the following guidelines:

This is not a place to publish a discussion, editorial, or requests to debug your code. Your issue will only be visible by you and problem moderators. Other users will not be able to view or reply your issues.
Do not submit duplicated issues. If you have already submitted one, please wait for an moderator to review it. Submitting multiple issues will not speed up the review process and might cause your account to be banned.
Issues must be filed in English or Chinese only.
Be sure your issue is related to this problem. If you need to submit an issue regarding another problem, contest, category, etc., you should submit it to the corresponding page.

Active Issues 0

No issues in this category.

Closed/Resolved Issues 0