सुंदर बिट-स्ट्रिंग्स
हमें बिट-स्ट्रिंग्स बहुत पसंद हैं। विशेष तौर पर, अगर किसी बिट-स्ट्रिंग में k लगातार 0 न हों, तो हम उसे खासतौर पर सुंदर मानते हैं। दिया गया है कि बिट-स्ट्रिंग की लंबाई n है, तो क्या आप उन सभी अलग-अलग बिट-स्ट्रिंग्स की गिनती कर सकते हैं जो लंबाई n में सुंदर होंगी?
इनपुट
इनपुट में दो पूर्णांक n और k दिए जाते हैं (1 ≤ k ≤ n ≤ 1000)।
आउटपुट
कार्यक्रम को लंबाई n की उन सुंदर बिट-स्ट्रिंग्स की संख्या प्रिंट करनी चाहिए। चूँकि उत्तर बहुत बड़ा हो सकता है, आपको इसे से मोड्यूलो (modulo) करके 출력 करना होगा।
उदाहरण
इनपुट | आउटपुट |
|---|---|
5 2 | 24 |
व्याख्या
00100
00101
00110
00111
01001
01010
01011
01100
01101
01110
01111
10010
10011
10100
10101
10110
10111
11001
11010
11011
11100
11101
11110
11111
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB