문제
부터 까지 번호가 적힌 종이를 명의 사람 등에 붙여져 있다. 번호를 바탕으로 명의 사람에게 자리를 다음과 같은 규칙으로 배치해주려고 한다.
이러한 규칙을 만족하며 명의 사람을 일렬로 앉히는 경우의 수를 구하는 프로그램을 작성하라.
예제 설명
총 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로 나눈 나머지를 출력한다.