题目描述

可怜的小珅还是小学生，刘老师就给他出了一道题。这道题给出了一个 $n$ 和 $p$，让他求 $(1! + 2! + 3! + \dots + n!) \bmod p$ 的值。

小珅算了一个小时都没算完，他已经崩溃了。于是他找到了你，想让你帮忙解决这道疯狂的题。

注：$n!$ 表示 $n$ 的阶乘，即 $1 \times 2 \times \dots \times n$。

输入格式

输入只有一行，包含两个正整数 $n$ 和 $p$。

输出格式

输出只有一行，即为式子的值。

5 1000

153

7 10

3

1000000000000000 9999999

8611659

数据规模与约定

对于 $20\%$ 的数据，$1 \le n \le 1000$。

对于 $50\%$ 的数据，$1 \le n \le 10000000$。

对于 $100\%$ 的数据，$1 \le n \le 10^{16}$，$1 \le p \le 10000000$。