SP5143 BNYINT - Binary Integer

请点击[这里](http://www.spoj.com/content/john_jones:hangzhou2008.pdf)下载比赛题目的 PDF 版本。题目是 PDF 中的 B 题。请注意，在 SPOJ 上必须使用标准输入输出。 --- 最近发现了一台拥有 $\binom{N}{3}$ 个开关的古董机器，能够处理 $0 \ldots 2^N - 1$ 范围内的整数。每个开关对应一个二进制表示中正好有三个 1 的整数。如果你选择将编号为 $X_0, X_1, \ldots, X_{M-1}$ 的开关打开，那么任何经过机器的整数 $Y$ 会被转换为 $Y \oplus X_0 \oplus X_1 \oplus \ldots \oplus X_{M-1}$ 的结果（$\oplus$ 表示按位异或运算）。 我们想知道，有多少种恰好可以利用 $K$ 个开关将整数 $S$ 转换为整数 $T$ 的配置。请你编写程序，帮助我们计算这种配置的数量。

输入包含多个测试用例。 每个测试用例由两个整数 $N$ 和 $K$ 开始（$1 \le N \le 40，0 \le K \le \min\{20, \binom{N}{3}\}$），接着是两个各由 $N$ 位组成的二进制整数 $S$ 和 $T$。 相邻测试用例之间用空行分隔。当出现 $N = 0$ 和 $K = 0$ 时，表示输入结束，此时不需要进行处理。

对于每个测试用例，输出一个整数，表示可以将第一个整数变为第二个整数的方案总数。由于结果可能很大，请输出结果对 $10007$ 取模后的值。 **本翻译由 AI 自动生成**