꼬리별

긴 꼬리를 남기며 밤하늘을 지나가는 꼬리별을 본 적이 있는가? 사실 이 꼬리는 먼지나 기체가 아니라, 별의 주민들이 일부러 만들어 뿌리는 마법 가루이다. 이 별의 주민들은 족제비처럼 생겼으며, 정성을 다해 꼬리를 만든다는 뜻으로 스스로를 '다꼬리'라고 부른다.

꼬리별의 1년은 $P$일로 나뉘어 있고, 별에는 1번부터 $P$번까지 번호가 붙은 $P$마리의 다꼬리가 살고 있다. 마법 가루의 양에 비해 다꼬리의 수가 부족해서, 다꼬리들은 다음 규칙에 따라 야근을 한다.

• 1번 다꼬리는 연봉 지급을 담당하므로, 매년 첫 날에만 야근을 한다.
• 그 외의 $i$번($2 \le i \le P$) 다꼬리는 매년 $i$의 배수 번째 날에 야근을 하되, $i$번째 날은 제외한다.

위 규칙에 따르면 1년 중 몇몇 날은 모든 다꼬리가 정시에 퇴근한다. 그런 날마다 그 날짜를 그 해의 연도만큼 거듭제곱한 값이 다꼬리들의 연봉에 누적된다. 이 값은 천문학적으로 큰 수이지만, 아쉽게도 다꼬리들이 받는 연봉은 이 값을 $P$로 나눈 나머지이다.

다꼬리들이 규칙에 따라 한 해 동안 열심히 일했을 때 받게 되는 연봉을 구하여라.

첫 줄에 꼬리별의 한 해를 이루는 날의 수이자 별에 살고 있는 다꼬리의 수인 정수 $P$($2 \le P \le 10^9$, $P$는 소수)와 올해 연도를 나타내는 정수 $Q$($0 \le Q \le 1{,}000$)가 공백을 사이에 두고 주어진다.

첫 줄에 올해 한 해 동안 일한 다꼬리들이 받게 되는 연봉을 출력한다.