Problem D
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.
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 |
