Welcome to ZOJ
Information
Select Problem
Runs
Ranklist
ZOJ Problem Set - 3791
An Easy Game

Time Limit: 2 Seconds      Memory Limit: 65536 KB

One day, Edward and Flandre play a game. Flandre will show two 01-strings s1 and s2, the lengths of two strings are n. Then, Edward must move exact k steps. In each step, Edward should change exact m positions of s1. That means exact m positions of s1, '0' will be changed to '1' and '1' will be changed to '0'.

The problem comes, how many different ways can Edward change s1 to s2 after k steps? Please calculate the number of the ways mod 1000000009.

Input

Input 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 ≤ mn). The second line of each case is a 01-string s1. The third line of each case is a 01-string s2.

Output

For each test case, you should output a line consist of the result.

Sample Input

3 2 1
100
001

Sample Output

2

Hint

100->101->001
100->000->001

Author: CHEN, Zemin
Source: ZOJ Monthly, June 2014
Submit    Status