#6609. 无意识的石子堆 加强版

内存限制:512 MiB 时间限制:2000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: rvalue

题目描述

古明地恋(koishi)和小石子(koishi)是好朋友。

这天,恋恋在钓鱼的时候钓到了 2n 颗一模一样的小石子。
她把小石子带回地灵殿后,发现姐姐古明地觉刚好做了一个 n\times m 的网格给宠物们当做游戏场地,其中 n\le m

恋恋打算看着手里的 2n 颗小石子,突然想把这些石子放到网格中。
恋恋发现她刚好有 2n 颗石子,所以她不希望有任意一行或一列中有超过 2 颗石子。
因为恋恋会无意识地行动,她自己也不知道自己下一步要怎么放棋子。但是好奇心旺盛的她想知道自己有多少种不同的放石子的方案。
她对巨大的数字不感兴趣,她只想知道方案数除以她无意识想到的质数 943718401 后的余数。

于是恋恋给你打了个电话打算让你满足她的好奇心。

少女打call中...

输入格式

一行两个整数 n,m 。含义如题目描述所述。

输出格式

一行一个整数,表示方案数除以 943718401 后的余数。

样例

样例输入 1

3 3

样例输出 1

6

样例输入 2

4 4

样例输出 2

90

样例输入 3

223 514

样例输出 3

682238370

数据范围与提示

由于一些原因,本题采用子任务制。你必须通过某一 Subtask 中的所有测试点才能获得这个 Subtask 的分数。

Subtask # 分值 n m 特殊限制
1 10 \le 5 \le 5 N/A
2 10 \le 2000 \le 2000
3 10 \le 1\times 10^5 \le 1\times 10^5 n=m
4 15 m-n\le 10
5 25 N/A
6 30 \le 2\times 10^6 \le 1\times 10^{18}