Hamming Ellipses

In geometry an ellipse is defined by two focal points $f_1$, $f_2$ and a length $D$. The ellipse is the set of all points $p$ with $d(f_1, p) + d(f_2, p) = D$.

The usual setting for an ellipse is the Euclidean plane with the Euclidean distance.

This problem uses a different kind of ellipse. The space here is the space of words of length $n$ over an alphabet of $q$ distinct symbols, written $\mathbb{F}_q^n$. For given $q$ and $n$ there are $q^n$ points, that is words, in $\mathbb{F}_q^n$.

The distance measure is the Hamming distance. The Hamming distance $d_H(x, y)$ between two words $x, y \in \mathbb{F}_q^n$ is the number of positions where the symbols of $x$ and $y$ differ. For example, the Hamming distance between the words 01201 and 21210 is 3, because the words carry different symbols in three positions. The Hamming distance between any two words in $\mathbb{F}_q^n$ is always an integer between 0 and $n$, inclusive.

Inside $\mathbb{F}_q^n$ the Hamming ellipse is the set of all points $p$ with $d_H(f_1, p) + d_H(f_2, p) = D$. Given $q$ and $n$, the two focal points $f_1$ and $f_2$, and the distance $D$, determine how many points $p \in \mathbb{F}_q^n$ 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 2n$).

The second and third lines give the two focal points $f_1$ and $f_2$ in that order. Each line is a string of length $n$ over the digits $\{0, 1, \dots, q-1\}$.

Print one line with a single integer, the number of points on the ellipse. The input is chosen so that the answer is less than $2^{63}$.