TFG was watching the chess world's championship with his brother VH and they got in the mood to play chess. VH learned an opening move called "sicilian", but TFG didn't like it, because VH didn't understand the suffering that the knight had to bear. To get VH to understand that, TFG used an application made for cellphones that he created that was able to turn his brother into a chess's knight. However, due to an unknown bug, his brother got stuck on the cellphone's numerical keypad, instead of being trapped on a chess table. TFG quickly fixed the bug, but since his brother was suffering, he told his brother that would only turn him back into his human shape if he solved the following problem:
"How many distinct phone numbers $S$, of length $N$, can he create by moving as a horse on the keypad, starting on the number $K$?"
VH must start on the position $K$ (without pressing this key), and then he must move to a position that could be reached by a chess knight, if the keypad was a chess table. When he moves to another position, the key of this position is pressed and the digit is added to the string. He keeps going until the $N$ digits are stored.
However, TFG said that this problem was actually pretty easy. To make things more interesting, he told his brother another number $T$, of length $M$, and wants to know how many different numbers $S$ can he create, of length $N$, such that there is no occurrence of $T$ in $S$ (i.e. $T$ is not a substring of $S$).
The cellphone keypad has the following shape:
$123$
$456$
$789$
$. 0.$
($.$ denotes an invalid position)
Since the chess knight moves on $L$-shaped paths (two moves in one direction and one move on the other one). For example, from the position $1$ he could go to $6$ or $8$.
Since the answer can be very large, you must output its remainder when divided by $10^9 + 7$.
The first line contains three integers $N$, $M$ and $K$ ($1 <= N <= 10^4$, $0 <= M <= 100$ e $0 <= K <= 9$). The second line contains a string $T$, representing a phone number, with $M$ digits ($0 <= T_i <= 9$).
You must output a single number, the amount of distinct phone numbers of $N$ digits that doesn't contain $T$ as a substring, modulo $10^9 + 7$.
In the first sample, the possible numbers are: $43$, $48$, $60$, $61$ and $67$. Despite the horse being able to create the number $40$ starting from $0$, it is not a valid phone number due to the given restrictions.
## Input
The first line contains three integers $N$, $M$ and $K$ ($1 <= N <= 10^4$, $0 <= M <= 100$ e $0 <= K <= 9$). The second line contains a string $T$, representing a phone number, with $M$ digits ($0 <= T_i <= 9$).
## Output
You must output a single number, the amount of distinct phone numbers of $N$ digits that doesn't contain $T$ as a substring, modulo $10^9 + 7$.
[samples]
## Note
In the first sample, the possible numbers are: $43$, $48$, $60$, $61$ and $67$. Despite the horse being able to create the number $40$ starting from $0$, it is not a valid phone number due to the given restrictions.
**Definitions**
Let $ T \in \mathbb{Z} $ be the number of test cases.
For each test case $ k \in \{1, \dots, T\} $, let $ A_k = (a_{k,1}, a_{k,2}, a_{k,3}, a_{k,4}) $ be a 4-tuple of integers, where $ a_{k,i} \in \{0, 1, \dots, 100\} $ denotes the number of visits to the $ i $-th scenic spot.
**Constraints**
1. $ 1 \le T \le 10^4 $
2. For each $ k \in \{1, \dots, T\} $ and $ i \in \{1,2,3,4\} $: $ 0 \le a_{k,i} \le 100 $
**Objective**
For each test case $ k $, let $ s_k = \sum_{i=1}^{4} \mathbb{I}(a_{k,i} > 0) $ be the number of distinct scenic spots visited.
Classify the traveller based on $ s_k $:
- If $ s_k = 0 $, output "_Typically Otaku_"
- If $ s_k = 1 $, output "_Eye-opener_"
- If $ s_k = 2 $, output "_Young Traveller_"
- If $ s_k = 3 $, output "_Excellent Traveller_"
- If $ s_k = 4 $, output "_Contemporary Xu Xiake_"