题目描述

情人节到了，Facer 收到了女朋友亲手制作的一盒巧克力。

盒子中有 $N$ 种不同类型的巧克力。从 $N$ 种类型中任选 3 种不同类型，可以组成一种“三种巧克力混合”的盘子，因此一共有：

种不同的盘子。Facer 预先为每一种三元组合都准备了恰好一盘，因此每种组合最多只能被选择一次。

随后，Facer 和他的女朋友分别从每种类型中至多选择一块巧克力，组成各自的初始集合。

接下来，Facer 从之前准备好的 $\binom N3$ 盘混合巧克力中，恰好选择 $M$ 个不同的盘子，把这些巧克力加入自己的集合。

最后，Facer 不断进行如下操作：

• 如果某一种类型的巧克力至少有两块，就吃掉其中两块。

一直操作到每种类型最多只剩一块巧克力为止。

Facer 希望最终剩下的巧克力类型集合与女朋友的初始集合完全相同。

请计算选择这 $M$ 个盘子的方案数。

输入格式

输入包含多组测试数据。

每组测试数据第一行包含两个整数 $N,M$：

接下来两行各包含一个长度为 $N$ 的 01 串：

• 第一行表示 Facer 的初始巧克力集合；
• 第二行表示他女朋友的初始巧克力集合。

第 $i$ 位为 1 表示初始集合中含有第 $i$ 种巧克力，为 0 表示不含。

当输入：

0 0

时结束，且该组数据不需要处理。

输出格式

对每组测试数据输出一行，表示合法选择方案数对 $10007$ 取模后的结果。

样例

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

1
1
6