#P6940. 分身
分身
分身(path)
时间限制:2秒;空间限制:512 MiB。
题目描述
你有 个分身和 个目的地。街区构成网格图,用 表示一个街区。第 个分身从 出发,前往第 个目的地 。
每一步只能从 走到 或 。任意两个分身的路径不能经过同一个街区,起点和终点也包括在内。
求所有分身到达各自目的地且路径两两不相交的方案数。两种方案不同,当且仅当至少一个分身的路径不同。答案对 取模。
输入格式
从标准输入读入。第一行一个整数 ;第二行 个整数 。
输出格式
向标准输出写出一行,一个整数,表示答案。
样例输入
2
1 2
样例输出
3
数据范围
所有数据满足 ,,。