Time limit: 1 second
Memory limit: 256 MB
King Xerxes - the King of Spadana - recently a string of long ciphers
n
n has received apadana from a friendly and neighboring country.

First, we define two types of fields.

A string is called a block if it consists of one of the lowercase letters of the alphabet plus a natural number (without leading zero). For example
a
123
a123 and
f
4
f4 are block but
1
a
1a and
a
b
1
ab1 and
a
02
a02 and
a
12
b
a12b and
12
a
12a are not blocks. (Note that the natural number must come after the letter)

A string is called a generator if it consists of one or more blocks. For example
a
12
b
4
d
7
a12b4d7 is a productive string.

We define the beauty of a generator string by the number of digits minus the number of letters. For example, the beauty of the string
a
12
b
4
d
7
a12b4d7 equals
1
1 is the beauty of the field
a
123
b
5
a123b5 equal
2
is 2.

Apadana country works like this to send a cipher string:

They first consider a generating string, say this string of
t
t block is formed. string
r
e
s
Consider res which is initially null. they
t
t perform the following operation step:

at the stage
i
i th letter related to the block
i
i is considered and that letter at the end
r
e
s
res are added. Then string
r
e
s
res as the number corresponding to the block
i
They repeat iam and string
r
e
s
res will be created. Finally after doing
t
t stage, string
r
e
s
res is the cipher string.

For example, if the generator string equals
a
1
b
2
c
4
be a1b2c4, then after done
t
=
3
t=3 steps:
ϕ
→
a
→
a
b
a
b
→
a
b
a
b
c
a
b
a
b
c
a
b
a
b
c
a
b
a
b
c
ϕ→a→abab→ababcababcababcababc
password string
a
b
a
b
c
a
b
a
b
c
a
b
a
b
c
a
b
a
b
c
ababcababcababcababc is obtained.

Khashayar Shah has given a secret thread to Kivan - the great advisor - and asks him to find out if there is a productive thread whose beauty
k
be k and make the cipher string?

After many investigations, Keyvan has understood that the length of the code string
n
n is but only
m
m, the first letter of this string has reached the hands of Xerxeshah and
n
-
m
The remaining n−m letters are not specified. Now a slightly confused Kevan asks you to find the number of productive threads that

their beauty
k
be k
The length of the cipher string corresponding to them
n
be n and
m
The first letter m should be equal to the string that reached the hands of King Xerxes.
Since this number may be large, take its remainder
1
0
9
+
7
10
9
 Find +7.

input
In the first line, enter three numbers
n
,
m
,
k
n,m,k is ready.

Then if
m
>
0
Let m>0 be a string of length
m
m has come that
m
m specifies the first letter of the cipher string.

1
≤
n
≤
100

000
1≤n≤100 000
0
≤
m
≤
n
0≤m≤n
0
≤
k
≤
1
0
9
0≤k≤10
9


The input string consists of only lowercase letters of the English alphabet.

output
Print the answer to the problem in the only output line.

Sub-problems
Constraint score subproblem
1 30
n
≤
1

000
n≤1 000
220 input strings of letters only
a
a is formed.
350 without additional restrictions
Example
Sample entry 1
2 2 0
aa
Plain text
Sample output 1
2
Plain text
Sample input 2
4 2 0
ab
Plain text
Sample output 2
677
Plain text
Sample entry 3
2 0 0
Plain text
Sample output 3
702         write code in python 3.12