You have a quantum computer containing two binary strings $s$ and $t$, both of length $n$. Every second, $x$ of the $n$ bits on $s$ are randomly chosen and flipped. Find the probability that after $K$ seconds, $s$ will become $t$.

Input Specification

The first line contains three integers, $n$, $x$, and $K$.

The next line contains the string $s$.

The last line contains the string $t$.

Output Specification

Find the probability of turning $s$ into $t$. If the probability is $\frac{A}{B}$, print $A{B}^{-1}(\mathrm{mod}{10}^9+7)$. It can be proven that the result is rational.

Constraints

$0\le x\le n$, $0\le K$, $1\le n$.

Subtask	Score	Constraints
1	10%	$n\le 6$, $K\le 100$
2	12%	$n\le 7$, $K\le 700000$
3	18%	$n\le 10$, $K\le 900000$
4	12%	$n\le 16$, $K\le {10}^9$
5	48%	$n\le 128$, $K\le {10}^9$

Sample Input 1

4 1 2
0000
0000

Sample Output 1

250000002

Explanation For Sample 1

The probability is $\frac{1}{4}$.

Sample Input 2

4 2 1
0000
0000

Sample Output 2

0

Sample Input 3

6 4 3
010000
100000

Sample Output 3

932444451

Sample Input 4

6 1 43
010000
011110

Sample Output 4

242545047

Sample Input 5

6 3 0
010000
010000

Sample Output 5

1

Sample Input 6

1 1 9
0
1

Sample Output 6

1