P6191 [USACO09FEB] Bulls And Cows S

The annual fair is coming. Farmer John wants to arrange $N$ ($1 \leq N \leq 10^5$) cows and bulls in a single line. John has noticed that the bulls have been very aggressive lately; if two bulls are too close in the line, they will argue and end up fighting, ruining the peaceful atmosphere.

John is very resourceful. He has determined that there must be at least $K$ ($0 \leq K \lt N$) cows between any two bulls in order to avoid fights. John wants you to help him calculate how many different arrangements can avoid any fighting. John considers all bulls identical and all cows identical. Therefore, as long as the positions of different types of cattle are different, the arrangements are considered different.

Two integers $N$ and $K$.

Output the number of ways John can arrange them. Since this number may be very large, output the result modulo $5\,000\,011$.

Below are the 6 feasible arrangements that FJ came up with ($C$ stands for cow, $B$ stands for bull). - CCCC - BCCC - CBCC - CCBC - CCCB - BCCB Translated by ChatGPT 5