해밍 타원

기하학에서 타원은 두 초점 $f_1$, $f_2$와 길이 $D$로 정의된다. 타원은 $d(f_1, p) + d(f_2, p) = D$를 만족하는 모든 점 $p$의 집합이다.

타원이라고 하면 보통 유클리드 거리를 쓰는 2차원 유클리드 평면 위의 도형을 떠올린다.

이 문제는 다른 종류의 타원을 다룬다. 여기서 쓰는 공간은 서로 다른 기호 $q$개로 이루어진 알파벳으로 만든 길이 $n$의 단어 전체가 이루는 공간이고, $\mathbb{F}_q^n$으로 적는다. $q$와 $n$이 주어지면 $\mathbb{F}_q^n$의 점, 즉 단어는 $q^n$개다.

거리는 해밍 거리를 쓴다. 두 단어 $x, y \in \mathbb{F}_q^n$ 사이의 해밍 거리 $d_H(x, y)$는 같은 자리의 기호가 서로 다른 위치의 개수다. 예를 들어 단어 01201과 21210의 해밍 거리는 3이다. 기호가 다른 위치가 세 곳이기 때문이다. $\mathbb{F}_q^n$의 두 단어 사이의 해밍 거리는 항상 0 이상 $n$ 이하의 정수다.

이제 $\mathbb{F}_q^n$ 안에서 해밍 타원을 $d_H(f_1, p) + d_H(f_2, p) = D$를 만족하는 모든 점 $p$의 집합으로 정의한다. $q$와 $n$, 두 초점 $f_1$과 $f_2$, 거리 $D$가 주어질 때 이 해밍 타원 위에 놓인 점 $p \in \mathbb{F}_q^n$의 개수를 구하라.

첫째 줄에 세 정수 $q$ ($2 \le q \le 10$), $n$ ($1 \le n \le 100$), $D$ ($1 \le D \le 2n$)가 주어진다.

둘째 줄과 셋째 줄에 두 초점 $f_1$과 $f_2$가 순서대로 주어진다. 두 줄은 모두 숫자 $\{0, 1, \dots, q-1\}$로 이루어진 길이 $n$의 문자열이다.

타원 위에 놓인 점의 개수를 정수 하나로 한 줄에 출력한다. 입력은 답이 $2^{63}$보다 작도록 주어진다.