[ABC360] E - Random Swaps of Balls

E - Random Swaps of Balls

Time Limit: 2 sec / Memory Limit: 1024 MB

分数：450分

题面

有个白球和一个黑球。这个球排成一排，黑球最初位于最左边。

高桥将执行以下操作次。

• 在到之间均匀随机选择两个整数。设选择的整数为和。如果，则交换从左边数第个和第个球。

经过次操作后，黑球在从左边数第个位置。求取模下的期望值。

将期望值取模的结果是多少？可以证明，所求期望值始终为有理数。此外，在此问题的限制条件下，可以证明，如果将此值表示为不可约分数，则。因此，存在唯一的整数，使得，其中。报告这个。

限制条件

---

输入

从标准输入中以如下格式给出：

输出

在一行中输出答案。

---

输入样例 1

2 1

输出样例 1

499122178

进行一次操作后，黑球位于从左边数第1个位置和第2个位置的概率均为。因此，期望值为。

---

输入样例 2

3 2

输出样例 2

554580198

---

输入样例 3

4 4

输出样例 3

592707587