题目描述

给定 \(n,p\) ,求 \(\dfrac {n!}{Π_{pi<=n}^{i=1}pi}\mod p\) 的值。

格式

输入格式

一行两个数 \(n,p\) 。

输出格式

一行一个数答案。

样例1

样例输入1

4 3

样例输出1

2

样例解释

原式=\(\dfrac {4!} {\Pi_{3i<=4}^{i=1}3i \mod 3}=1*2*4 \mod 3=8 \mod 3=2\)。

限制

对于\(50\%\)的数据， \(n<=10^6,p<=10^3\)

对于\(100\%\)的数据，\(1<=n<=10^{18},p<=10^6\) 且保证 \(p\) 为质数

提示

\(n<=10^{18}\)使得你的程序需要极高的时间效率