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

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

Sample Input 1 | Sample Output 1 |
---|---|

3 5 9 01201 21210 |
24 |

Sample Input 2 | Sample Output 2 |
---|---|

4 6 5 123031 231222 |
0 |

Sample Input 3 | Sample Output 3 |
---|---|

2 32 32 01010101010101010101010101010101 01010101010101010101010101010101 |
601080390 |