Problem C
Hamming Ellipses

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 $\mathrm{distance}(f_1,p)+\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 $\mathrm{hammingdistance}(f_1,p)+\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 2n$).

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\dots 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}$.

3 5 9
01201
21210

24

4 6 5
123031
231222

0

2 32 32
01010101010101010101010101010101
01010101010101010101010101010101

601080390