====== N포커 ======

===== 풀이 =====
  * N장중에서 포카드가 1종류 이상 포함된 경우의 수를 구하면 된다.
  * [[ps:포함배제의 원리]]를 이용하면, 아래처럼 계산하면 된다..
    * {1포카드가 포함된 경우}, ... , {13포카드가 포함된 경우} 를 더하고
    * {1포카드와 2포카드가 포함된 경우}, {1포카드와 3포카드가 포함된 경우}, ... , {12포카드와 13 포카드가 포함된경우} 를 빼고
    * {1,2,3 포카드가 포함된 경우}, {1,2,4 포카드가 포함된 경우}, ... , {11,12,13포카드가 포함된경우} 를 더하고
    * ...
  * X포카드가 포함된 경우의 수는. 4장을 X로 채우고, 나머지 N-4장은 52-4장중에서 고르면 되니까 C(52-4, N-4). X의 가짓수는 13개
  * X,Y포카드가 포함된 경우의 수는. 8장을 X,Y로 채우고, 나머지 N-4장은 52-4장중에서 고르면 되니까 C(52-8, N-8). (X,Y)의 가짓수는 C(13,2)개
  * ...
  * 이제 식을 정리하면 C(13,1)*C(52-4,N-4) - C(13,2)*C(52-8,N-8) + C(13,3)*C(52-12,N-12) - ....  = sigma{(-1)^(i-1) * C(13,i)*C(52-i*4,N-i*4)} 을 계산해주면 된다. N-4*i 가 양수인 동안만 계산하면 된다
  * 시간복잡도는 항 한개를 계산하는데는 전체 카드 장수에 비례하는 시간이 걸리는데 전체 카드 장수는 52로 고정되어있으므로 그냥 상수취급해도 된다. 항이 N/4 개이므로 그냥 전체 복잡도는 O(N) 

===== 코드 =====
<dkpr py>
"""Solution code for "BOJ 16565. N포커".

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

Tags: [Inclusion-Exclusion Principle]
"""

import math

MOD = 10007


def main():
    N = int(input())
    answer = 0
    for i in range(1, N // 4 + 1):
        count = math.comb(13, i) * math.comb(52 - 4 * i, N - 4 * i)
        answer += count if i % 2 else -count
    print(answer % MOD)


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


{{tag>BOJ ps:problems:boj:골드_1}}