## Canada Day Contest 2021 - 0-1

View as PDF

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

Author:
Problem types

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

#### Input Specification

The first line contains three integers, , , and .

The next line contains the string .

The last line contains the string .

#### Output Specification

Find the probability of turning into . If the probability is , print . It can be proven that the result is rational.

, , .

1 10%
2 12%
3 18%
4 12%
5 48%

#### Sample Input 1

4 1 2
0000
0000

#### Sample Output 1

250000002

#### Explanation For Sample 1

The probability is .

#### 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