{"problem":{"name":"[CCPC 2023 北京市赛] 勿蹖宠物","description":{"content":"Ene 喜欢回文。 Ene 现在有一些单词。她想选出若干个单词并将它们首尾相连，形成长度恰好为 $L$ 的回文串。每个单词都可以选择多次，也可以不选。 Ene 想知道这样做的方案数。Ene 认为两个方案不同，当且仅当各单词出现次数不同或它们的排列顺序不同，注意多种不同的方案可能会得到同一个回文串。由于答案可能会很大，你需要将答案对 $1,000,000,007$ 取模。","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1500,"memory_limit":1048576},"difficulty":{"LuoguStyle":"P6"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP10047"},"statements":[{"statement_type":"Markdown","content":"Ene 喜欢回文。\n\nEne 现在有一些单词。她想选出若干个单词并将它们首尾相连，形成长度恰好为 $L$ 的回文串。每个单词都可以选择多次，也可以不选。\n\nEne 想知道这样做的方案数。Ene 认为两个方案不同，当且仅当各单词出现次数不同或它们的排列顺序不同，注意多种不同的方案可能会得到同一个回文串。由于答案可能会很大，你需要将答案对 $1,000,000,007$ 取模。\n\n## Input\n\n输入的第一行包含两个正整数 $N, L$，分别表示单词的数量和需要组成的回文串的长度。保证 $1\\le N\\le 333$，$1\\le L\\le 1000$。\n\n接下来 $N$ 行，每行输入一个字符串 $s_i$，表示一个单词。保证 $1\\le |s_i| \\le L$，$\\sum_{i=1}^N |s_i| \\le 600$；输入的单词仅包含小写字符，且互不相同。\n\n## Output\n\n输出一个非负整数，表示组成回文串的方案数对 $1,000,000,007$ 取模后的结果。\n\n[samples]\n\n## Note\n\n**【样例解释 1】**\n\n有以下五种方案：\n\n- `stack` `cats`\n- `evil` `olive`\n- `eel` `eve` `lee`\n- `lee` `eve` `eel`\n- `eve` `eve` `eve`\n\n**【样例解释 2】**\n\n有以下两种方案：\n\n- `a` `a`\n- `aa`","is_translate":false,"language":"English"}],"meta":{"iden":"LGP10047","tags":["2023","省赛/邀请赛"],"sample_group":[["7 9\ncats\neel\neve\nevil\nlee\nolive\nstack","5"],["2 2\na\naa","2"],["6 12\naa\naab\nno\non\npets\nstep","43"]],"created_at":"2026-03-03 11:09:25"}}