파댕이의 케이크 만들기

• 문제의 조건을 만족하는 순서의 갯수 p는, dyck word 문제를 k개의 알파벳으로 확장한 형태이다. 이는 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).

"""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()