In geometry, ellipses are defined by two focal points f₁, f₂ and a length D. The ellipse consists of all points p such that distance(f₁, p) + distance(f₂, p) = D.</p>

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. As you can probably see, for given values of q and n, there are qⁿ different words (points) in the space Fⁿ_q.

For a distance measure, we use the Hamming distance. The Hamming distance between two words x, y ∈ Fⁿ_q 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 will always be an integer between 0 and n, inclusive.

Within the space Fⁿ_q, we now define the Hamming ellipse as the set of all points p such that hammingdistance(f₁, p) + hammingdistance(f₂, p) = D. Given values q and n, focal points f₁ and f₂ and distance D, we ask you to determine the number of points p ∈ Fⁿ_q that lie on this Hamming ellipse.

입력 형식

The first line contains three integers q (2 ≤ q ≤ 10), n (1 ≤ n ≤ 100) and D (1 ≤ D ≤ 2n).</p>

The second and third lines specify the two focal points f1 and f2, each formatted as a string of length n using digits {0, 1 . . . 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⁶³.

예제 입력 1

3 5 9
01201
21210

예제 출력 1

24

예제 입력 2

4 6 5
123031
231222

예제 출력 2

0

예제 입력 3

2 32 32
01010101010101010101010101010101
01010101010101010101010101010101

예제 출력 3

601080390