Bajtazar 喜欢打桥牌，但他在把手中的牌迅速整理好方面遇到了一些困难。因此，在下一次和朋友们打牌之前，他决定练习一下整理扑克牌。

为此，他准备了一副特殊的训练用牌，共有 $n$ 张牌，编号从 $1$ 到 $n$。练习从洗牌开始，这会在他手中形成一个给定的排列。接下来，他希望把这些牌整理成编号递增的顺序。

只要牌还没有排好序，Bajtazar 就会执行如下操作：他查看手中第一张牌的编号（记为 $k$），然后在手中找到编号为 $k-1$ 的那张牌（如果 $k=1$，则寻找编号为 $n$ 的牌），并把这张牌移动到最前面。执行这一操作所需的时间与被找到的牌距离序列开头的距离成正比。整理完牌所需的总时间等于所有执行操作的时间之和。

例如，排列 $5\ 6\ 3\ 7\ 1\ 4\ 2$ 的整理时间为 $5 + 3 + 6 + 6 = 20$，因为连续的操作如下：

$$5\,6\,3\,7\,1\,\underline{4}\,2 \xrightarrow[]{5} 4\,5\,6\,\underline{3}\,7\,1\,2 \xrightarrow[]{3} 3\,4\,5\,6\,7\,1\,\underline{2} \xrightarrow[]{6} 2\,3\,4\,5\,6\,7\,\underline{1} \xrightarrow[]{6} 1\,2\,3\,4\,5\,6\,7$$

Bajtazar 希望对所有 $n!$ 种可能的排列都进行这样的排序练习。请你编写一个程序，劝阻他这个想法，计算完成这一壮举所需的总时间。首先，只需要求出总时间对给定整数 $m$ 取模后的结果即可。

输入格式

输入的第一行也是唯一一行包含两个整数 $n$ 和 $m$ （$2 \le n \le 1\ 000\ 000$，$2 \le m \le 1\ 000\ 000\ 000$）。

输出格式

输出一行，表示使用 Bajtazar 的方法对所有排列进行排序的总时间对 $m$ 取模后的结果。

样例数据

对于输入数据：

2 100

正确的输出是：

1

样例说明

共有两种排列： $1\ 2$（时间 $0$）以及 $2\ 1$（时间 $1$）。

测试 “ocen”：

• 1ocen：$n = 3$, $m = 100$，答案为 $15$；
• 2ocen：$n = 10$, $m = 1000$，答案为 $100$；
• 3ocen：$n = 500$, $m = 100\ 000$，答案为 $60\ 000$；
• 4ocen：$n = 100\ 000$, $m = 1000$，答案为 $0$。

子任务

测试集划分为以下子任务。每个子任务的测试由一组或多组测试数据组成。