 # Permudrome

Let s be a string consisting of lowercase English letters. There exist M restrictions of the form ai bi, (1 ≤ i ≤ M), meaning that letters ai and bi are not allowed to be placed on adjacent positions (two positions are adjacent if their absolute difference is 1).

Your task is to compute the number of permutations of s which respect all M restrictions, and, in addition, are palindromes. Since the answer can be fairly large, you should compute this number modulo 666013.

Note: a permutation is defined by the string associated to it, not by the ordering of indices. For instance, the permutations aba and aba are considered to be the same even if you swap the a's, and should only be counted once.

### Input

The first line of input contains the string s.
The second line contains integer M.
Each of the following M lines contains a pair of space separated lowercase English letters.

### Output

A single integer: the number of valid palindrome permutations, modulo 666013.

• 2 ≤ |s| ≤ 30
• 0 ≤ M ≤ 30

### Samples

InputOutputExplanation
aaaabb
0
3There are 3 palindrome permutations:
• aabbaa
• abaaba
• baaaab
Note that there are no additional restrictions.
abcba
1
b c
1There are 2 palindrome permutations:
• abcba
• bacab
However, only the latter respects the b c restriction.
dpsidindspdaawiswiunndnuisdiss
1
i n
499393There are actually 1158696000 valid permutations, but we can't count that high.
Questions?