सुंदर बिट-स्ट्रिंग्स
हमें बिट-स्ट्रिंग्स बहुत पसंद हैं। विशेष तौर पर, अगर किसी बिट-स्ट्रिंग में
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