31738번 - 매우 어려운 문제

문제

제목과 다르게 이 문제는 아주 쉽다.

2 이상의 정수 $N,ドル $M$에 대하여, $N!$을 $M$으로 나눈 나머지를 구하여라.

입력

첫 번째 줄에 두 정수 $N$과 $M$이 공백으로 구분되어 주어진다.

출력

첫 번째 줄에 문제의 답에 해당하는 정수를 출력한다.

제한

• 2ドル \leq N \leq 10^{18}$ ($N$ 제한에 주의하라)
• 2ドル \leq M \leq 10^7$
• $N,ドル $M$은 정수이다.

노트

• $n!$은 1ドル$ 이상 $n$ 이하의 모든 정수의 곱을 의미하며 "$n$ 팩토리얼"이라고 읽는다. 즉, $n!=n\times(n-1)\times(n-2)\times\cdots\times2\times1$이다.
• 이 문제의 일부 테스트 케이스는 답의 범위가 2ドル^{31}$을 넘어갈 수 있으므로 long long 자료형을 쓰도록 하자.