Într-un şir de biţi, o secvenţă este o succesiune maximală nevidă de biţi alăturaţi identici. De exemplu, şirul 0011101 conţine patru secvenţe: 00, 111, 0 şi 1. Pentru orice secvenţă, lungimea sa este dată de numărul de biţi ai secvenţei. În exemplul de mai sus, cele patru secvenţe au lungimile 2, 3, 1 şi respectiv 1.
Cerinţă
Scrieţi un program care citeşte trei numere naturale N, T şi K şi determină numărul de şiruri de N biţi care conţin exact T secvenţe, orice secvenţă având lungimea între 1 şi K. Pentru că acest număr poate fi foarte mare, trebuie să determinaţi acest număr modulo 2011.
Date de intrare
Fişierul de intrare secvbiti.in conţine pe prima linie trei numere naturale N, T şi K, separate prin câte un spaţiu.
Date de ieşire
Fişierul de ieşire secvbiti.out va conţine o singură linie pe care veţi scrie numărul şirurilor de N biţi care conţin exact T secvenţe, fiecare secvenţă având lungimea cel mult K, modulo 2011.
Restricţii
4 ≤ N ≤ 2000
2 ≤ T ≤ N / 2
1 ≤ K ≤ N
Exemple
secvbiti.in
secvbiti.out
Explicaţii
5 2 4
8
Şirurile de 5 biţi care conţin exact 2 secvenţe, fiecare secvenţă având lungimea maxim 4 sunt: 00001, 11110, 00011, 11100, 00111, 11000, 01111, 10000. Evident, 8 mod 2011 = 8.