자리 배치
우측 버튼을 눌러 기기를 연결해주세요.
문제정보
자리 배치
100
참여자
46
정답률
34.7%
13
12

문제 


부터 까지 번호가 적힌 종이를 명의 사람 등에 붙여져 있다. 번호를 바탕으로 명의 사람에게 자리를 다음과 같은 규칙으로 배치해주려고 한다. 

  1. 맨 앞 자리에는 누가 앉아도 상관 없다. 만약 누군가 앉는다면 그 사람은 이상 이하의 정수 를 정하고, 모두가 들을 수 있도록 크게 말한다.
  2. 그 사람을 기준으로 뒤에 일렬로 앉되, 자신의 바로 앞에 앉은 사람의 번호가 자신의 번호와 비교하여 보다 작으면 안 된다.
  3. 그렇게 순서대로 명의 사람이 번의 규칙을 만족하며 모두 앉는다.

이러한 규칙을 만족하며 명의 사람을 일렬로 앉히는 경우의 수를 구하는 프로그램을 작성하라.


예제 설명


총 4명의 사람이 있고 가장 먼저 앉은 사람의 번호가 1, 그리고 K를 2로 정했다고 가정했을 때, 가장 먼저 앉은 1번 사람 바로 뒤에는 2, 3번 사람이 앉을 수 있다.
4번 사람은 자신의 번호 4가 1보다 3이나 크기 때문에 규칙에 어긋나므로 앉을 수 없다.
만약 1번 사람 바로 뒤에 3번 사람이 앉았다면, 그 다음 3번 사람 뒤에는 2, 4번 모두가 앉을 수 있다. 그 이후로 만약 [1, 3, 4, 2]와 같이 앉았다면 이는 규칙을 만족한다. 하지만 [2, 1, 4, 3]과 같이 앉았다면 4번 바로 앞이 1번이기 때문에 규칙에 어긋난다.
규칙을 만족하면서, 총 개의 자리 배치 경우의 수가 있다.


입력


첫째 줄에 사람의 수 과 맨 앞 사람이 정하는 수 입력한 수식이 여기에 나타가 공백으로 구분되어 주어진다.



출력


규칙을 만족하며 명의 사람을 일렬로 앉히는 경우의 수를 출력한다.
이때, 경우의 수가 너무 커질 수 있으므로 1000000007로 나눈 나머지를 출력한다.

입/출력 예시
:
공백
:
줄바꿈
:
예시 1
입력
42
출력
18
예시 2
입력
9997997
출력
739068098
⋇ 입출력 형식을 잘 지켜주세요
Q&A
누구나 질문하고 답변할 수 있는 Q&A입니다. 문제를 풀며 어려웠던 부분에 대해 질문해보세요.
이 문제에 관한 질문 (0)