수학IV에서는 경우의 수를 세는 방법을 배우고 다양한 문제를 풀어본다. 여러분이라면 이 문제도 풀 수 있을 것이다!
부터 까지의 수가 하나씩 적힌 카드 장이 일렬로 놓여 있다. 왼쪽부터 번째 위치를 번 위치라고 부른다. 처음에 번 위치에는 가 적힌 카드가 있다.
시준이는 다음 연산을 정확히 번 한다.
매 연산에서 를 고르는 방법은 가지이므로, 번의 연산을 하는 방법은 모두 가지다. 어떤 번째 연산에서 고른 가 하나라도 다르면, 두 방법을 서로 다른 방법으로 본다.
번의 연산을 모두 마친 뒤 번 위치에 가 적힌 카드가 있으면, 그 카드를 제자리 카드라고 한다. 또, 어떤 방법으로 번의 연산을 마쳤을 때 제자리 카드의 개수를 그 방법의 점수라고 한다. 가능한 가지 방법의 점수를 모두 더한 값을 구하라.
첫 번째 줄에 양의 정수 가 공백으로 구분되어 주어진다.
두 번째 줄에 개의 양의 정수 이 공백으로 구분되어 주어진다.
문제의 정답을 로 나눈 나머지를 출력한다. 이 수는 소수이다.
1번의 연산 이후에 제자리 카드는 1개이며, 총 3가지의 연산이 가능하니 답은 3이다.
