# An Easy Game

Time Limit: 2 Seconds

Memory Limit: 65536 KB

## Description

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


None