405634: GYM102020 A Awesome Brother

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:

$$$1 2 3$$$

$$$4 5 6$$$

$$$7 8 9$$$

$$$. 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 \le N \le 10^4$$$, $$$0 \le M \le 100$$$ e $$$0 \le K \le 9$$$). The second line contains a string $$$T$$$, representing a phone number, with $$$M$$$ digits ($$$0 \le T_i \le 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$$$.

2 2 0
40

5

3 2 0
40

10

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.