Kabobs

Anna wants to open a restaurant called "Candy Mountain" that serves candy only. The menu has one dish, a candy kabob: a stick holding several pieces of food, eaten from the tip to the base.

While Anna eats a kabob, once a run of consecutive pieces forms one pattern she expects to meet another pattern in the part she has not eaten yet. Once she eats a piece of apple immediately followed by a piece of banana, she expects a leaf of mint immediately followed by chocolate somewhere later in the kabob. Any position among the remaining pieces makes her happy.

Here is a kabob Anna likes.

Apple-Banana-Watermelon-Plum-Watermelon-Plum-Watermelon-Mint-Chocolate

Drawn as a picture:

Anna has written down the rules for the new restaurant, and she worries that they allow too many kabobs. Each rule has the form "b implies e afterwards", where b and e are non-empty strings of characters that stand for pieces of food. The rule b>e means that if the pattern b appears in the kabob, then e appears somewhere after it. Every character of b must appear consecutively for the rule to trigger, and every character of e must appear consecutively to satisfy it. The last character of b and the first character of e do not have to be adjacent; the first character of e only has to sit after the last character of b. No piece of food appears twice in one rule, so b and e share no character and no character repeats inside b or inside e. One piece of food may appear in several rules.

If b appears several times in a kabob, every occurrence needs an e after it. One e placed after all occurrences of b is enough.

In a ruleset, rules are separated by | and each rule is written as u>v. Here u and v are strings of letters and digits, and no character appears twice in one rule. For example, the ruleset AB>X|R>A|T>B holds three rules:

• every AB needs an X after it;
• every R needs an A after it;
• every T needs a B after it.

Under this ruleset the kabobs SBSB, REA, ABX, BA, ABXBA, RRA, TBTB, RTABX are valid, while RAT, TAB, ABXAB are not.

Count the kabobs of length $K$ that satisfy every rule. Each position of a kabob holds one piece from $S$, and the same piece may be used in several positions.

The first line contains the kabob length $K$, a space, and a non-empty string $S$ of the pieces available for a kabob. $S$ consists of letters and digits ('A' to 'Z', 'a' to 'z', '0' to '9'), and no character appears twice in $S$.

The second line contains a non-empty string $R$ that holds a ruleset in the form described above. $R$ contains no spaces, and the patterns in $R$ use characters from $S$ only.

$1 \le K \le 500$ and $3 \le |R| \le 60$.

Print, on one line, the number of kabobs of length $K$ that satisfy every rule in $R$, modulo 10000000.