ऐरे को भरना
एक
n तत्त्वों वाले ऐरे पर विचार करें। आपको पता है कि इसमें मौजूद सभी मान 1 से m के बीच हैं। इसके अतिरिक्त, दो क्रमिक तत्त्वों के बीच का परिमाणात्मक अंतर अधिकतम 1 हो सकता है। ऐरे के कुछ मान मिटा दिए गए हैं, और आपका काम यह पता लगाना है कि इन मिटाए गए स्थानों को उल्लिखित शर्तों का पालन करते हुए कितने अलग-अलग तरीकों से भरा जा सकता है।इनपुट
इनपुट की पहली पंक्ति में दो पूर्णांक
n (1 ≤ n ≤ ) और m (1 ≤ m ≤ 100) दिए जाते हैं।अगली पंक्ति में
n स्पेस-सेपरेटेड पूर्णांक होते हैं (1 ≤ ≤ m), जो ऐरे के तत्त्वों को दर्शाते हैं। यदि किसी का मान 0 है, तो इसका मतलब है कि उस स्थान पर मौजूद मान हटा दिया गया था।आउटपुट
ऐरे को सभी शर्तों का पालन करते हुए भरने के कुल तरीकों की संख्या प्रदर्शित करें। यह संख्या बहुत बड़ी हो सकती है, इसलिए उत्तर को से मॉड लेकर प्रिंट करें।
उदाहरण
इनपुट | आउटपुट |
3 5
2 0 2 | 3 |
व्याख्या
- 2 1 2
- 2 2 2
- 2 3 2
Constraints
Time limit: 6 seconds
Memory limit: 512 MB
Output limit: 1 MB