<|instruction|>
Solve the below problem. The solution should start with an abridged problem statement. Then key observations. Then full solution based on the observations. Then C++ and Python implementations with comments.

310. Hippopotamus
Time limit per test: 0.5 second(s)
Memory limit: 65536 kilobytes
input: standard
output: standard



After fixing your roof, you still think that it looks unpretty. So you opt for a new one, consisting of n consecutive long narrow boards. You have two types of boards: wooden ones and iron ones, giving you an amazing total of 2n possible roofs.

But the safety should not be left aside. Having considered the weight and the cruising speed of a falling hippopotamus, you decide to have at least k iron boards among every m consecutive boards.

How many possibilities do you have?

Input
The input file contains three integers, n, m and k, separated by spaces and/or line breaks. 1 ≤ n ≤ 60, 1 ≤ m ≤ 15, 0 ≤ k ≤ m ≤ n.

Output
Output the number of possibilities.

Example(s)
sample input
sample output
10 2 1
144

sample input
sample output
5 5 2
26

sample input
sample output
3 2 2
1

<|response|>
1. Abridged Problem Statement  
Count the number of binary strings S of length n (boards: wooden=0, iron=1) such that in every contiguous block of m bits there are at least k ones.

2. Key Observations  
- Any valid string of length n is fully determined by its prefix and the sliding‐window constraint on every block of length m.  
- Since m≤15, there are at most 2^m≈32768 possible patterns for any window of size m.  
- We can build the string one bit at a time and keep track of only the last m bits (a bitmask of size m).  
- We enforce the “≥k ones in each window” constraint as soon as each new window (of size m) is formed.

3. Full Solution Approach  
Define dp[i][mask] = number of valid prefixes of length i+m whose last m bits are exactly the bitmask mask. Here i ranges from 0 to n−m, so that i+m runs from m to n.

  a. Base Case (i=0):  
     We’ve chosen the first m bits arbitrarily as mask. This is valid only if popcount(mask)≥k.  
     For every mask in [0,2^m):
       if popcount(mask) ≥ k then dp[0][mask] = 1, else dp[0][mask] = 0.

  b. Transition (i → i+1):  
     We append a new bit b∈{0,1} to the prefix of length i+m, forming a prefix of length i+m+1.  
     Let old mask = dp[i]’s state.  
     Compute new_mask = ((old_mask << 1) | b) & ((1<<m)−1).  
     This shifts out the oldest bit, appends b, and keeps exactly m bits.  
     Check popcount(new_mask)≥k. If yes, add dp[i][old_mask] to dp[i+1][new_mask].

  c. Final Answer:  
     After filling dp up to i = n−m, sum all dp[n−m][mask] over mask∈[0,2^m). This is the total number of valid strings of length n.

Time Complexity: O((n−m+1)·2^m·2) = O(n·2^m).  
Memory: O((n−m+1)·2^m), reducible to O(2^m) by keeping only two rolling arrays.

4. C++ Implementation with Detailed Comments
```cpp
#include <bits/stdc++.h>
using namespace std;
using int64 = long long;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m, k;
    cin >> n >> m >> k;

    // Number of positions where we form a new window = n - m + 1
    int rows = n - m + 1;
    int M = 1 << m;  // total number of m-bit masks

    // dp_curr and dp_next: rolling arrays to save memory
    vector<int64> dp_curr(M, 0), dp_next(M, 0);

    // Base case: i = 0, first window of length m = mask
    for(int mask = 0; mask < M; mask++){
        if(__builtin_popcount(mask) >= k){
            dp_curr[mask] = 1;
        }
    }

    // Build up for i = 1 .. rows-1
    for(int i = 1; i < rows; i++){
        // Clear dp_next
        fill(dp_next.begin(), dp_next.end(), 0);

        // For each old mask, try to append 0 or 1
        for(int mask = 0; mask < M; mask++){
            int64 ways = dp_curr[mask];
            if(ways == 0) continue;

            // Append bit = 0 or 1
            for(int bit = 0; bit < 2; bit++){
                // Shift left, add new bit, keep m LSBs
                int new_mask = ((mask << 1) | bit) & (M - 1);
                // Enforce at least k ones in the new window
                if(__builtin_popcount(new_mask) < k) continue;
                dp_next[new_mask] += ways;
            }
        }

        // Move dp_next into dp_curr for next iteration
        dp_curr.swap(dp_next);
    }

    // Sum up all ways for the final row
    int64 answer = 0;
    for(int mask = 0; mask < M; mask++){
        answer += dp_curr[mask];
    }

    cout << answer << "\n";
    return 0;
}
```

5. Python Implementation with Detailed Comments
```python
import sys

def main():
    data = sys.stdin.read().split()
    n, m, k = map(int, data)

    rows = n - m + 1
    M = 1 << m  # total number of m-bit masks

    # dp_curr[mask]: number of valid prefixes of length i+m ending with 'mask'
    dp_curr = [0] * M
    dp_next = [0] * M

    # Base case: first window (i=0)
    for mask in range(M):
        if mask.bit_count() >= k:
            dp_curr[mask] = 1

    # Build DP for each subsequent window start i = 1 .. rows-1
    for _ in range(1, rows):
        # reset dp_next
        for j in range(M):
            dp_next[j] = 0

        # extend each current mask by 0 or 1
        for mask, ways in enumerate(dp_curr):
            if ways == 0:
                continue
            for bit in (0, 1):
                new_mask = ((mask << 1) | bit) & (M - 1)
                # check the new window has at least k ones
                if new_mask.bit_count() < k:
                    continue
                dp_next[new_mask] += ways

        # swap roles for next iteration
        dp_curr, dp_next = dp_next, dp_curr

    # final answer: sum of dp_curr over all masks
    print(sum(dp_curr))

if __name__ == "__main__":
    main()
```