Sentence Reconstructions
Given a dictionary and a text, count the ways to split the text into a sequence of dictionary words, modulo 109+7.
Input: the first line has D (dictionary size); the next D lines are the distinct words; the following line is the text.
Output: the number of segmentations mod 109+7.
Constraints:
- 1 ≤ D ≤ 1000
- 1 ≤ total word length ≤ 105
- 1 ≤ |text| ≤ 105
Sample Tests
Input 1
2 ab c abc
Output 1
1
Input 2
1 xy xyz
Output 2
0
Discussion (opens after you solve — no spoilers before)
No comments yet.