#YDRG012G. 不带壳
不带壳
题目描述
小周很喜欢 Dyck 路。有一天,她被邀请去到一个二维平面上游玩,所以需要规划一下游玩路径。因为小周是来游玩的,她的每一步必定停留在一个景点上。她想要规划出一条 Dyck 路作为自己的路径,但这些景点的位置有些特殊。具体地,一个点 为景点当且仅当 为非负整数且 。也就是说,这些景点在平面上排成了两排。小周最开始位于景点 。
在这样一个平面上行走实在是太简单了,就连小周都失去了规划路径的兴趣,任由概率带领她前行;她也不希望游览两次相同的景点。小周会从 开始,每次在和当前所在景点四联通的景点中均匀随机选取一个未被经过的景点,并走过去。如果不存在这样的景点,那么小周就会结束这一次游玩。令小周可能行走的一条路径为 ,记 为最终小周行走的路径为 的概率,并记 为 的长度或小周总共移动的次数, 为过程中景点 坐标的最大值。
在出发前,小周听说 坐标为 的两个景点有很美丽的风景,但她不希望自己很累,不想走多于 步。所以她就想知道,她走出一条 的路径 的概率,也就是
但小周的数学不太好,她不会算这个值,于是她来求助你了。小周保证答案是有理数,她也知道这个分数的分子分母都可能很大,所以你只需要输出这个分数对 取模的结果即可。具体地,假设答案为 ,其中 ,那么取 ,你只需要输出 。可以证明 必定存在。
输入格式
一行两个整数 。
输出格式
一行一个整数,表示答案。
样例输入 #1
10 6
样例输出 #1
988495873
样例 #2
样例输入 #2
65 32
样例输出 #2
394183784
样例 #3
样例输入 #3
191981 114514
样例输出 #3
427827207
数据范围
| Subtask | 分值 | 特殊性质 |
|---|---|---|
| 1 | 5 | |
| 2 | ||
| 3 | 10 | |
| 4 | ||
| 5 | 25 | |
| 6 | 45 | 无 |
对所有数据,,。
京公网安备 11011102002149号