시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 512 MB 6 4 4 66.667%

문제

In geometry, ellipses are defined by two focal points f1, f2 and a length D. The ellipse consists of all points p such that distance(f1, p) + distance(f2, 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 Fnq. As you can probably see, for given values of q and n, there are qn different words (points) in the space Fnq.

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

Within the space Fnq, we now define the Hamming ellipse as the set of all points p such that hammingdistance(f1, p) + hammingdistance(f2, p) = D. Given values q and n, focal points f1 and f2 and distance D, we ask you to determine the number of points p ∈ Fnq 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).

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 263.

예제 입력

3 5 9
01201
21210

예제 출력

24

예제 입력 2

4 6 5
123031
231222

예제 출력 2

0

예제 입력 3

2 32 32
01010101010101010101010101010101
01010101010101010101010101010101

예제 출력 3

601080390

힌트