SP10096 LIGHTS3 - Lights (Extreme)

**说明：** 建议先解决 LIGHTS2 问题再来挑战这道题。 John 有一个游戏，他有 $n$ 个灯泡和一个有 $n$ 个开关的控制板。每个灯泡都有开关状态，按下第 $i$ 个开关可以切换灯泡 $i$ 的状态（从开变为关，或者从关变为开）。在游戏中，John 每次可以选择一组开关（可能是空集）并按下，以此来反转对应灯泡的状态。 游戏开始时，所有灯泡都是关闭的。在总共进行 $m$ 次操作后，John 希望前 $v$ 个灯泡是打开的，而其他的灯泡是关闭的。如果不能做到这一点，他就会输掉游戏。需要注意的是，John 不允许在不同的操作中使用相同的开关组合。 这个游戏看起来很简单，因为有很多种获胜的方法。这激发了John的兴趣，他想尝试所有可能的获胜策略。请帮助他计算这样的获胜方法总数。两个游戏被认为是相同的，如果通过重新排列其中一个游戏的步骤后，在每一步中按下的开关组合都相同。 例如，如果 $n = 4$，$m = 3$，$v = 2$，一种可行的胜利策略是在第一步时按下开关 1、2 和 4；第二步按下开关 1 和 3；最后一步按下开关 1、3 和 4。这种策略与先按下开关 1 和 3；接着按下开关 1、2 和 4；最后按下开关 1、3 和 4 被视为等价的。

输入最多包含 1500 行，每行代表一个测试用例。每行包含三个整数 $n$（满足 $1 \le n \le 50$）、$m$（满足 $1 \le m \le 120$）和 $v$（满足 $0 \le v \le n$）。最后一行是 0 0 0，它不需要处理。

对于每个测试用例，输出一行，表示 John 可以通过比赛的方法数。结果需要对质数 $10\,567\,201$ 取模。 ## 样例输入 ``` 3 3 1 6 4 0 6 4 3 0 0 0 ``` **本翻译由 AI 自动生成**