문제

Div.1 참가자라면 잘 알겠지만 "쉬운", "간단한" 같은 단어가 쓰인 문제는 보통 쉽지 않다. 이 문제는 어떨까?

정수 배열 에 대해 는 에 없는 가장 작은 음이 아닌 정수를 의미한다. 예를 들어, , , 이다.

배열의 길이 과 수의 범위 이 주어진다. 배열의 길이가 이고, 모든 원소가 이상 이하를 만족하는 모든 정수 배열 중 하나를 임의로 선택할 때, 의 기댓값을 구하시오.

이때, 조건을 만족하는 배열의 선택될 확률은 모두 동일하다.

입력

첫째 줄에 배열의 길이와 수의 범위를 나타내는 두 정수 , 이 공백으로 구분되어 주어진다.

출력

의 기댓값이 일 때, 첫째 줄에 이고 인 정수 를 출력한다. 이러한 는 유일함을 증명할 수 있다.

노트

이 소수이므로 페르마의 소정리에 의해 이고 가 의 배수가 아니라면 이다.

예제 해설

첫째 예제에서, , 일 때 조건에 맞는 배열의 개수는 개이므로 각 배열이 선택될 확률은 이다. 인 배열은 개, 인 배열은 , , , , 개, 인 배열은 , 개이다. 가 이상인 배열은 없으므로 기댓값은 이며, 이므로 답은 이다.

셋째 예제에서, , 일 때 기댓값은 이다.