PROBLEM LINKS
DIFFICULTY
HARD
EXPLANATION
First, let’s reformulate the problem a bit. In fact, we have to find how many different bit strings of length N exist such that among every M consecutive bits there are at least K 1’s and the total number of 1’s is minimal possible for such strings.
Consider the case when N is divisible by M. In this case the string consists of N/M blocks of bits of length M, and by the problem statement we have to put at least K 1’s in each of these blocks, giving a total of N/M * K 1’s. But note that this is also minimum, since we can put these 1’s at the ends of blocks and thus satisfy the needed restrictions.
Now let’s make a table of size K x (N/M), where each column contains the positions of 1’s in the corresponding block from the start of that block in increasing order (so the maximal possible number in this table is M). For example, if N = 24, M = 6, K = 3 and our bit string is 000111 001101 100110 110100, then the table should look like this:
4 3 1 1
5 4 4 2
6 6 5 4
Obviously, the numbers in each column strictly increase. An important thing to note now: if there are two neighbouring numbers in one row such that the leftmost one is strictly less than the other one, then this string doesn’t meet the condition from the problem statement – between the corresponding 1’s there will be K-1 1’s and at least M positions, so any block of length M between them will have less than K 1’s. The reverse thing also holds: if the numbers in every row weakly decrease, then the bit string corresponding to the table will be correct. Thus if we find a way to count the number of such tables, we’ll also be able to count the number of needed bit strings.
From this moment on you may either try to find some pattern and finally get the needed formula (this has been successfully implemented by several contestants) or try to search the internet for something on this topic. In the latter case it’s useful to know that standard Young tableaux look similar to these tables. Then, Wikipedia article on the topic tells us that what we’re searching for are actually semistandard Young tableaux! (see http://en.wikipedia.org/wiki/Young_tableaux#Tableaux). A bit of further searching leads us to a hook-content formula which is exactly what we need (for example, it is described here). So we’re done. (and yes, searching “bijective proof of hook-content formula” gives quite a lot of results)
Well, not really. We still have to multiply and divide about a billion numbers. Fortunately, a lot of these numbers cancel each other. For example, let’s look what happens when N = 48, M = 6 and K = 3. The numbers to multiply are:
13 12 11 10 9 8 7 6
12 11 10 9 8 7 6 5
11 10 9 8 7 6 5 4
and the numbers we should divide the result by are:
10 9 8 7 6 5 4 3
9 8 7 6 5 4 3 2
8 7 6 5 4 3 2 1
It’s easy to see that a lot of columns cancel each other. Actually, there will be no more than M columns remaining in both tables, so there will be no more than M * K numbers to multiply and divide (note that division modulo prime number is also a well-known topic, for example look here).
Another way to perform this is precalculating factorials modulo 1 000 000 007 of all numbers, say, divisible by 500 000 (or less, still considering the source code limit). Now it’s easy to find any needed factorial in at most 500 000 multiplications, and we require no more than 100 of these factorials. This approach should be optimized well, though.
And we’re almost done. Don’t forget that we’ve solved the problem only when N is divisible by M. But in reality every possible case can be reduced to the case above. Suppose there are floor(N/M) blocks and P leftover positions. If P <= M-K, it means that there should be only 0’s in the first P positions of each block. If P >= M-K, it means that there should be only 1’s in the last M-P positions of each block (note that we must add one more block for those P positions then). Once P = M-K, both these cases are equivalent and the answer is always 1. This paragraph is easy to understand if you spend some time with a pen and paper.
This time, we’re absolutely done. Still there were some solutions using matrix exponentiation and possibly some other ideas. I would be happy to hear any alternative solutions or ideas to this problem in comments 
SETTER’S SOLUTION
Can be found here.
TESTER’S SOLUTION
Can be found here.