====== 폰친구 ======

===== 풀이 =====
  * [[ps:tutorial:composition#상하한이 모두 주어진 경우|상하한이 있는 Composition의 개수]] 를 구하는 문제이다. 링크에서 설명했듯이 [[ps:tutorial:PIE]]나 [[ps:tutorial:생성함수]]를 이용해서 식을 유도한 뒤에 O(N+K)에 구할수 있다.
  * 이 문제에서는 K<=N*M으로 주어지므로 시간복잡도가 O(N*M)

===== 코드 =====
<dkpr py>
"""Solution code for "BOJ 20296. 폰친구".

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

Tags: [combinatorics]
"""

from teflib import combinatorics

MOD = 10**9 + 7


def main():
    N, m, M, K = [int(x) for x in input().split()]
    print(combinatorics.count_compositions(K, N, MOD, lo=m, hi=M))


if __name__ == '__main__':
    main()

</dkpr>
  * Dependency: [[:ps:teflib:combinatorics#count_compositions|teflib.combinatorics.count_compositions]]

{{tag>BOJ ps:problems:boj:골드_3 ps:teflib:linear_homogeneous_recurrence}}