16941번 - 꼬리별

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

꼬리별의 1년은 P일로 나뉘어 있으며, 별에는 1번부터 P번까지 번호가 붙은 P마리의 다꼬리가 살고 있다. 만들어야 하는 마법 가루의 양에 비해 다꼬리의 수가 부족하기 때문에, 다꼬리들은 다음과 같은 규칙으로 야근을 한다.

• 1번 다꼬리는 연봉 지급을 담당하는 다꼬리라서 매년 첫 날만 야근을 한다.
• 그 외의 i(2 ≤ i ≤ P)번 다꼬리는 매년 i번째 날을 제외한 i의 배수 번째 날에 야근을 한다.

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

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

첫 줄에 꼬리별의 한 해를 이루는 날의 수이자 별에 살고 있는 다꼬리들의 수를 의미하는 정수 P(2 ≤ P ≤ 10⁹, P는 소수)와 올해 연도를 의미하는 정수 Q(0 ≤ Q ≤ 1,000)가 공백을 사이에 두고 주어진다.

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