시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 85 29 26 39.394%

문제

S는 다음과 같이 정의된다.

  • S(0, n) = n (모든 양의 정수 n)
  • S(k, n) = S(k-1, 1) + S(k-1, 2) + ... + S(k-1, n) (모든 양의 정수 k, n)

k와 n이 주어졌을 때, S(k, n)을 1,000,000,007로 나눈 나머지를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 k와 n이 주어진다. (1 ≤ k ≤ 50, 1 ≤ n ≤ 1,000,000,000)

출력

첫째 줄에 S(k, n)을 1,000,000,007로 나눈 나머지를 출력한다.

예제 입력 1

1 3

예제 출력 1

6

예제 입력 2

2 3

예제 출력 2

10

예제 입력 3

4 10

예제 출력 3

2002

출처