In geometry, ellipses are defined by two focal points $f_1, f_2$ and a length $D$. The ellipse consists of all points $p$ such that $\mathop {\mathrm{distance}}(f_1, p) + \mathop {\mathrm{distance}}(f_2, p) = D$.

When one normally thinks of ellipses, it is in the context of the Euclidean 2D plane, with the Euclidean distance as a distance measure.

This problem explores a different kind of ellipse. The space we will work in is the space of words of length $n$ using an alphabet of $q$ different symbols, often denoted as $F_ q^n$. As you can probably see, for given values of $q$ and $n$, there are $q^n$ different words (points) in the space $F_ q^n$.

For a distance measure, we use the Hamming distance. The Hamming distance between two words $x, y \in F_ q^n$ is simply the number of positions where the symbols that make up the words $x$ and $y$ differ. For example, the Hamming distance between words 01201 and 21210 is 3 because there are 3 positions where the words have different symbols. The Hamming distance between any two words in $F_ q^n$ will always be an integer between $0$ and $n$, inclusive.

Within the space $F_ q^n$, we now define the Hamming ellipse as the set of all points $p$ such that $\mathop {\mathrm{hammingdistance}}(f_1, p) + \mathop {\mathrm{hammingdistance}}(f_2, p) = D$. Given values $q$ and $n$, focal points $f_1$ and $f_2$ and distance $D$, we ask you to determine the number of points $p \in F_ q^n$ that lie on this Hamming ellipse.

-----Input-----
The first line contains three integers $q$ ($2 \le q \le 10$), $n$ ($1 \le n \le 100$) and $D$ ($1 \le D \le 2 n$).

The second and third lines specify the two focal points $f_1$ and $f_2$, each formatted as a string of length $n$ using digits $\{ 0, 1 \ldots q - 1\}$.

-----Output-----
Output one line containing a single integer, denoting the number of points on the ellipse.

The input is chosen such that the answer is less than $2^{63}$.

-----Examples-----
Sample Input 1:
3 5 9
01201
21210
Sample Output 1:
24

Sample Input 2:
4 6 5
123031
231222
Sample Output 2:
0

见题面

见题面