====== 파댕이의 케이크 만들기 ======

===== 풀이 =====
  * 문제의 조건을 만족하는 순서의 갯수 p는, dyck word 문제를 k개의 알파벳으로 확장한 형태이다. 이는 [[ps:카탈랑 수#변형 및 일반화|k차원 카탈랑 수]]에 해당한다는 사실을 알고 있으면 쉽게 풀수 있다. 
    * 이것은 (n*k)! * 0!*1!*..*(k-1)! / ( n!*(n+1)!*..*(n+k-1)! ) 로 구할 수있다
  * 모든 순서의 갯수 q는 (n*k)! / (k!)^n 이다.
  * 이제 p/q 를 계산하면 된다. 팩토리얼 값들을 다 전처리해서 쓴다고 치면, (n*k)! 까지 팩토리얼 값을 구해놓으면 그 값들을 가지고 p와 q를 O(k)와 O(logn)에 구할수 있다. 그러면 가장 시간이 오래걸리는 부분은 (n*k)! 를 구하는데에 걸리는 O(n*k)이다.
  * 하지만, 식을 다시 보면 p와 q에 모두 (n*k)! 이 들어가므로, 약분시킬수가 있다. 그러면 (n+k-1)! 까지만 팩토리얼 값을 구해놓는 것으로 충분하다. 시간복잡도는 O(n+k).

===== 코드 =====
<dkpr py>
"""Solution code for "BOJ 30984. 파댕이의 케이크 만들기".

- Problem link: https://www.acmicpc.net/problem/30984
- Solution link: http://www.teferi.net/ps/problems/boj/30984

Tags: [combinatorics]
"""


MOD = 1_000_000_007


def main():
    N, K = [int(x) for x in input().split()]

    fact = [x := 1] + [x := x * i % MOD for i in range(1, N + K)]
    answer = pow(fact[K], N, MOD)
    for i in range(K):
        answer = answer * fact[i] * pow(fact[N + i], -1, MOD) % MOD

    print(answer)


if __name__ == '__main__':
    main()
</dkpr>

{{tag>BOJ ps:problems:boj:플래티넘_2}}