Description

When Xiao Z left home, he forgot his wallet, and the dropped coins lined up on the table. Xiao D, who is waiting for her older brother to come back, sits by the table and idly flips the coins.

Out of a personal preference, Xiao D always flips exactly $M$ coins at the same time in each operation. Since Xiao D is a thoughtful elementary school student, after doing this several times she quickly came up with a question: in how many ways can the coins be transformed from the original state to the current state in exactly $K$ flips?

Because Xiao D is a diligent student, she only needs you to tell her the number of ways modulo $10^9+7$ so that she can check her work.

Input Format

• The first line contains three integers $N$, $K$, $M$, representing the number of coins, the number of flips, and the number of coins flipped each time.
• The second and third lines each contain a string of length $N$, representing the initial state and the final state. Character '1' denotes heads, and '0' denotes tails.

Output Format

Output a single integer, the number of ways modulo $10^9+7$.

3 2 1
100
001

2

Hint

• Sample explanation:

There are two ways:

• $100 \to 101 \to 001$;

• $100 \to 000 \to 001$.

• Constraints:

  • For $30\%$ of the testdata, $N \le 4$, $0 \le K \le 5$.
  • For $60\%$ of the testdata, $N \le 10$.
  • For $100\%$ of the testdata, $1 \le N \le 100$, $0 \le K \le 100$, $0 \le M \le N$.

Translated by ChatGPT 5