Bajtazar is a well-known prankster from Bajtock – he makes a living by arranging various funny situations, which he then documents in the form of videos published on the internet. This time, he has set his sights on a large neon sign on the roof of a prestigious hotel with a very long name.

The letters of the neon sign form an $n$-letter string $w$, which is the name of the hotel. Bajtazar intends to break onto the hotel roof at night and turn off some of the neon letters so that the remaining illuminated letters, read from left to right, form a certain very funny $m$-letter word $s$. For the whole thing to look impressive, the positions of the last illuminated letter and the first illuminated letter must differ by at least $k$. The prankster wonders how many ways he can turn off the letters to achieve his goal.

Formally, he is interested in the number of ways to choose indices $j_1, j_2, \dots, j_m$ from the interval $[1, n]$ such that $j_1 < j_2 < \dots < j_m$, $j_m - j_1 \geq k$, and $w_{j_1}w_{j_2} \dots w_{j_m} = s$, where $w_i$ denotes the $i$-th letter of the string $w$. The indices $j_1, j_2, \dots, j_m$ correspond to the positions of the letters that will remain illuminated.

Input

The first line of the input contains three integers $n, m, k$ ($1 \leq k \leq n \leq 100\,000$, $1 \leq m \leq 10$). The second line contains the $n$-letter word $w$ displayed on the hotel roof. The third line contains the $m$-letter word $s$ that is to be displayed after turning off some letters. The words $w$ and $s$ consist only of lowercase English letters (a-z).

Output

In the only line of the output, print the required number of ways Bajtazar can achieve his goal, modulo $10^9 + 7$.

Examples

Input 1

13 3 5
longlonghotel
lol

Output 1

5

Note 1

Bajtazar can leave the letters illuminated at one of the following sets of positions: $\{1, 2, 13\}$, $\{1, 6, 13\}$, $\{1, 10, 13\}$, $\{5, 6, 13\}$, $\{5, 10, 13\}$.