An acronym is made of up the initial letter(s) of the words in a phrase, such as EU (European Union) and BREXIT (BRitish EXIT). In this problem, we can also either ignore or consider the conjunction "and", and the following adpositions "in", "on", "at", "to", "of", "from", "for" and "with" when making the acronym, such as BENELUX (BElgium, NEtherlands and LUXembourg) and RADAR (RAdio Detection And Ranging).

Given an acronym A, and a list of N strings W₁, W₂ ... W_N, you would like to find out the number of possible combinations of making the given acronym by using all the N strings following their order. That is, the acronym must be made up of at least one initial letter of each word, except the above-mentioned conjunction and adpositions (either skip or use it). Both A and the N strings only consist of lowercase latin letters. Since the answer can be large, output the answer modulo 1000000007.

Note: This is a harder version of the problem ACRYM, with larger constraints. Please read the input section carefully.

Input

The first line is the number of test cases T. (1 ≤ T ≤ 20)

For each test case, it starts with one integer N. (1 ≤ N ≤ 200)

Next line is a string A. (1 ≤ |A| ≤ 50000)

Following N lines, each consisting of one string W_i. (1 ≤ |W_i| ≤ 250)

It is guaranteed that W₁ is neither conjunction nor adposition.

Output

Output one integer indicating the number of possible combinations.

Example

Input:
3
3
duckhim
duck
hello
moto
7
natiofforessaa
national
office
for
forest
safety
in
aachen
4
whiskey
what
is
secret
key

Output:
0
4
1

Explanation

In case 1, no combination is possible.

In case 2, there are four possible combinations:

• NATIonal OFfice for FORESt SAfety in Aachen
• NATIonal OFfice for FORESt Safety in AAchen
• NATIonal Office For FORESt SAfety in Aachen
• NATIonal Office For FORESt Safety in AAchen

In case 3, only one possible combination exists:

• WHat Is Secret KEY