Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register
北京大学《ACM-ICPC竞赛训练》暑期课面向全球招生。容量有限,报名从速!
Language:
Facer's Chocolate Dream
Time Limit: 1000MSMemory Limit: 65536K
Total Submissions: 441Accepted: 170

Description

"It is so sweet to have chocolates on St. Valentine's Day!" Little Facer was so excited when he receives a box of self-made chocolates from his girlfriend, and he decided to eat these chocolates in a special way to commemorate this important day. Suppose that there are N types of chocolates in the box, it can be easily calculated that there are totally {{n}\choose{3}} different combinations if we choose 3 chocolates of different types to make a dish. Facer will first make one dish for every of these combination, so there will be {{n}\choose{3}} dishes in all with 3×{{n}\choose{3}} chocolates totally. Then both Facer and his girlfriend choose some chocolates of different types as their original chocolates set. After that, Facer choose exactly M dishes of three-type-mixed-chocolates which he made in the first step and add them into his original chocolates set. Finally, Facer continues eatting two chocolates of the same type until he cannot find any pair of chocolates of the same type (which means for each type of chocolates, there remains at most one chocolate). Facer wishes that his remaining chocolates set could be identical with his girlfriend's original chocolates set after the steps mentioned above, but he does not know the number of ways to choose dishes. Could please tell him the answer?

Input

The input consists of multiple test cases. Each test case starts with two integers, N and M, which are the number of different types of chocolates and the number of three-type-mixed-chocolates dishes Facer will choose, it is guaranteed that 1≤N≤1000, 0≤M≤1000. The following two lines contain one N-bit binary integer each, which represents Facer's and his girlfriend's original chocolates set. A case with N=0 and M=0 indicates the end of the input file, which should not be processed.

Output

For each test case, print one line containing one single integer, which represents the total number of ways to choose dishes. Since the number can be extremely big, you are only required to output the answer % 10007.

Sample Input

4 3
1101
1001
3 1
101
010
5 3
11010
10111
0 0

Sample Output

1
1
6

Hint

This problem is inspired from 2008 Regional Hangzhou but is more difficult.
A naive print-table-algorithm will not pass.

Source

[Submit]   [Go Back]   [Status]   [Discuss]

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator