28093번 - 비밀의 채팅방

문제

SCSC에는 고인물들이 채팅을 하고 노는 채팅방이 존재한다. 고인물들은 그 방에서 비밀의 문장으로 대화하고 있다. 고인물들이 사용하는 단어의 길이는 모두 정확히 $N$이며, 단어를 구성할 수 있는 글자의 개수는 $M$개이다. 고인물들은 다음과 같은 규칙으로 문장을 구성한다.

1. 문장을 구성할 단어들을 선택한다. 각 단어는 문장에서 최대 1번씩만 사용할 수 있다.
2. 단어들을 사전 순으로 오름차순 정렬한다.
3. 정렬된 단어들을 순서대로 이어 붙여 문장을 만든다. 아무런 단어도 사용하지 않은 문장("")도 문장으로 인정한다.

고인물들은 만든 모든 단어를 사전 순으로 정렬한 목록 $\{S_1,S_2,...,S_{M^N}\}$에서 각 단어 $S_i$에 담긴 비밀의 힘을 $F_i$라고 할 때 $F_i = i$가 성립하며, 각 문장에 담긴 비밀의 힘은 $(문장에 사용된 단어의 비밀의 힘의 총합)\bmod,円M$이 된다는 사실을 알아내었다! 고인물들은 문장에 담긴 비밀의 힘이 0ドル$이 될 확률 $p_M / q_M$에 대해 채팅방의 비밀번호를 $p_M \times q_M^{-1} \pmod{10^9 + 7}$로 설정하였다. 채팅방의 비밀번호는 한 번 설정하면 변경할 수 없으며, $q_M^{-1}$은 $q_M$의 모듈러 곱셈에 대한 역원이고, $p_M \times q_M^{-1} \pmod{10^9 + 7}$의 값은 주어진 제약 조건 내에서 유일하게 존재함을 증명할 수 있다.

어느 날 고인물들은 동아리방에 놀러온 뉴비들을 만나게 되었다! 뉴비들을 만나 신이 난 고인물들은 뉴비들에게 비밀의 채팅방 문화를 물려주고자 한다. 하지만 비밀의 채팅방 문화를 뉴비들에게 그대로 전파해주기에는 $M$이 너무 크다고 생각한 고인물들은 오랜 계산 끝에 $K$개의 글자를 사용해야 가장 적은 수의 글자로 기존의 비밀번호 생성 규칙을 위배하지 않을 수 있다는 사실을 알아내었으며, 이 $K$ 값을 뉴비들에게 알려주려고 한다! 즉 $S = \{S_1,S_2,...,S_{K^N}\}$에 대해 $p_M \times q_M^{-1} \equiv p_K \times q_K^{-1} \pmod{10^9 + 7}$가 성립해야 한다.

입력

첫째 줄에 $N$과 $M$이 주어진다. $(1 \le N \le 10^9$; 1ドル \le M \le 10^5)$

출력

사용해야 하는 최소 글자 수 $K$를 출력한다. 이때 $K = M$이라면 $K$ 대신 Smart Oldbie를 출력한다. $K$는 1 이상이어야 한다.

제한

힌트