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