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 ~AB^{-1}\pmod{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 700\,000~
3	18%	~n \le 10~, ~K \le 900\,000~
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