CLZSTRNG - String Problem

Mr. Avantgarde has 2 binary strings s1 and s2. He wants to convert s1 into s2. But this task isn't as easy as it looks. He has to convert s1 to s2 in exactly k steps. In each step, he can select exactly m chars and xor each of them by 1. Help him to find in how many ways can he convert s1 into s2 by using method described above. Output answer modulo 1000000009.

Constraints

Test cases <= 10

Length of s1 = length of s2 <= 100

m <= length of string

k <= 100

Input

First line will contain number of test cases. First line of test case contains s1. Second line of test case contains s2. Third line of test case contains m and k.

Output

For each test case, output result in a new line.

Sample

Input:
2
000
111
1 3
000
110
2 4

Output:
6
20

Added by:CSI
Date:2014-10-15
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64

hide comments
2015-05-15 07:49:16 Sergio Vieri
Length of s1=length of s2<=100
Is 100 here also in binary?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.