A receipt system expands a compact macro string into readable text by splitting it into known macro tokens. Given a dictionary of tokens and a target string, count how many distinct ways the target can be segmented into an ordered sequence of dictionary tokens, where each token may be reused any number of times. Two segmentations are different if they cut the string at a different set of positions. Because the count can be large, output it modulo 1000000007.
Input format
Line 1: an integer k, the number of dictionary tokens.
Line 2: k space-separated distinct dictionary tokens.
Line 3: the target string s.
Output format
A single integer: the number of valid segmentations of s, taken modulo 1000000007.
Constraints
- 1 <= k <= 20
- 1 <= length of each token <= 20
- 1 <= length of
s<= 300 - All strings consist of lowercase English letters only.