
134  ZOJ Monthly, June 2014  D
One day, Edward and Flandre play a game. Flandre will show two 01strings s_{1} and s_{2}, the lengths of two strings are n. Then, Edward must move exact k steps. In each step, Edward should change exact m positions of s_{1}. That means exact m positions of s_{1}, '0' will be changed to '1' and '1' will be changed to '0'. The problem comes, how many different ways can Edward change s_{1} to s_{2} after k steps? Please calculate the number of the ways mod 1000000009. InputInput will consist of multiple test cases and each case will consist of three lines. The first line of each case consist of three integers n (1 ≤ n ≤ 100), k (0 ≤ k ≤ 100), m (0 ≤ m ≤ n). The second line of each case is a 01string s_{1}. The third line of each case is a 01string s_{2}. OutputFor each test case, you should output a line consist of the result. Sample Input3 2 1 100 001 Sample Output2 Hint100>101>001 100>000>001 Author: CHEN, Zemin 