$n$ 名选手正在参加一场淘汰赛。比赛由一系列共 $n - 1$ 场对局组成。每场对局由两名选手对抗，其中一人输掉并被淘汰（即他不能再参加后续的任何对局），另一人获胜且不被淘汰。最后一场对局被称为决赛，因为它由仅剩的两位未被淘汰的选手进行。任意两场连续的对局，只要其中没有一场是决赛，就不能有共同的参赛选手。

一共有多少种不同的可能淘汰赛？如果存在一对选手，他们在其中一种淘汰赛中相互对局过，但在另一种中没有，则认为这两种淘汰赛是不同的。

输出正确答案模质数 $m$ 的值。形式化地，如果实际答案为 $y$，而你的答案为 $x$，当 $-2^{63} \le x < 2^{63}$ 且 $x - y$ 能被 $m$ 整除时，你的答案将被视为正确。

输入格式

唯一的一行包含两个整数 $n$ 和 $m$（$2 \le n \le 10^6$，$10^6 + 3 \le m \le 10^9 + 9$，$m$ 为质数），分别表示选手人数和模数。

输出格式

输出一个整数——可能淘汰赛的数量模 $m$ 的值。

样例

输入样例 1

2 1000003

输出样例 1

1

输入样例 2

3 756871351

输出样例 2

3

输入样例 3

4 79415263

输出样例 3

12

输入样例 4

10 62493391

输出样例 4

37074959

输入样例 5

228 602495767

输出样例 5

489051459

输入样例 6

1000 347390201

输出样例 6

71907364

输入样例 7

3228 172329319

输出样例 7

92438468

输入样例 8

10000 288002747

输出样例 8

214265262

输入样例 9

32228 839393021

输出样例 9

778284082

输入样例 10

100000 625953467

输出样例 10

462027594

输入样例 11

322228 493329803

输出样例 11

424612739

输入样例 12

1000000 1000000009

输出样例 12

195243062