Canada Day Contest 2021 - 0-1

View as PDF

Submit solution


Points: 20 (partial)
Time limit: 1.0s
Memory limit: 512M

Author:
Problem types

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

Comments

There are no comments at the moment.