Hide

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

Please log in to submit a solution to this problem

Log in