시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 1 1 1 100.000%

문제

호그볼트 수리마법과에 재학중인 서녕미온느는 올해 학교를 졸업한다. 상근 포터는 서녕미온느를 매우 심하게 괴롭혔고, 서녕미온느는 졸업을 하기 전에 상근 포터의 컴퓨터를 해킹하려고 한다.

상근 포터의 비밀번호는 1부터 N까지 자연수로 이루어진 순열이다. 상근 포터는 자연수 K에 집착한다. 예를 들어, 처음 보는 사람을 만났을 때, 그는 그 사람에게 자기 이름을 K번 말한다. 서녕미온느는 상근 포터가 비밀번호 치는 장면을 대학 재학동안 꾸준히 봤고, 그의 비밀번호의 순서는 K라는 사실을 알게되었다.

x ∈ {1, ..., N}의 모든 x를 상근 포터의 비밀번호에서 x가 있는 위치의 수로 K번 바꿨을 때, 다시 원래 x로 돌아오는 가장 작은 K를 순열의 순서라고 한다. 예를 들어, 순열이 2 3 1인 경우 1 → 3 → 2 → 1, 2 → 1 → 3 → 2, 3 → 2 → 1 → 3이기 때문에, 순열의 순서는 3이다.

N과 K가 주어졌을 때, 상근이의 비밀번호로 가능한 순열의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 100, 1 ≤ K ≤ 231 - 1)

출력

1부터 N까지 숫자로 이루어진 순열 중 순서가 K인 것의 개수를 231 - 1로 나눈 나머지를 출력한다. 

예제 입력

15 12

예제 출력

1789014075

힌트