N Poker
Time limit1sMemory limit256 MB
Count 52-card N-subsets containing a rank's four suits, output the count mod 10,007.
- Level
Medium7 of 10
- Topics
- Combinatorics, Math, Dynamic programming, Implementation
- Solved
- No attempts yet
Problem
Jeongyeon decided to make a new game that can be played with a deck of playing cards.
The game is played one-on-one between a dealer and a player. The player draws N cards from the 52 playing cards laid out. If the drawn cards can form a "four of a kind," the player wins; if not, the dealer wins and the game ends. However, Jeongyeon has not yet decided the number of cards to draw, N, for a fair game.
To help Jeongyeon make the decision easily, write a program that outputs the number of cases in which the player wins when N cards are drawn.
A deck of playing cards consists of the following 52 cards.
Figure: 트럼프 카드 (Playing Card)의 구성
4 suits: ♥, ♠, ◆, ♣, 13 ranks: A, 2, 3, 4, 5, 6, 7, 8, 9, 10, J, Q, K
Total 4 x 13 = 52 cards
A four of a kind means that among the drawn N cards, there exist "4 cards with the same rank and different suits." Also, the number of cases in which the player wins means the number of cases in which the N cards contain at least one such card combination.
Input
The first line gives the number of cards to draw, N. (1 ≤ N ≤ 52)
Output
On the first line, output the number of cases in which the player wins when N cards are drawn, modulo 10,007.