翻硬币

• 时间限制：1 秒
• 内存限制：128 MiB

题目描述

桌上有 $N$ 枚排成一列的硬币。每次操作必须同时翻转其中恰好 $M$ 枚硬币。

给定所有硬币的初始状态和目标状态，求恰好进行 $K$ 次操作后从初始状态变为目标状态的方案数。

答案对 $10^9+7$ 取模。

输入格式

第一行包含三个整数 $N,K,M$，分别表示硬币数量、操作次数和每次操作翻转的硬币数量。

第二行包含一个长度为 $N$ 的 01 字符串，表示硬币的初始状态。

第三行包含一个长度为 $N$ 的 01 字符串，表示硬币的目标状态。

其中 1 表示正面，0 表示背面。

输出格式

输出一行一个整数，表示方案数对 $10^9+7$ 取模后的值。

样例输入 1

3 2 1
100
001

样例输出 1

2

样例解释

存在两种方案：

• $100\to101\to001$；
• $100\to000\to001$。

数据范围

对于全部数据，保证 $1\le N\le 100$，$0\le K\le 100$，$0\le M\le N$。

上述三层由来源给出的 30%、60%、100% 累计范围转换为增量分值，未改变原限制语义。