반복 합 구하기

함수 $S$를 다음과 같이 정의한다.

• 모든 양의 정수 $n$에 대해 $S(0, n) = n$
• 모든 양의 정수 $k$, $n$에 대해 $S(k, n) = S(k-1, 1) + S(k-1, 2) + \dots + S(k-1, n)$

즉 $S(k, n)$은 한 단계 아래 함수의 값을 $1$부터 $n$까지 모두 더한 값이다.

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

첫째 줄에 $k$와 $n$이 공백으로 구분되어 주어진다. ($1 \le k \le 50$, $1 \le n \le 1{,}000{,}000{,}000$)

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