पथ विवरण
आपको एक
n x n ग्रिड दिया गया है। एक पथ (1, 1) सेल से शुरू होता है, सभी सेल का भ्रमण करता है, और (n, 1) सेल पर समाप्त होता है। यह पथ केवल दाएँ (R), बाएँ (L), ऊपर (U), या नीचे (D) दिशाओं में ही बढ़ता है, और प्रत्येक सेल को अधिकतम एक बार ही विज़िट कर सकता है। इस पथ का वर्णन LRUD वर्णों द्वारा किया गया है, जहाँ प्रत्येक वर्ण अपनी संबंधित दिशा दर्शाता है।
हालाँकि, इस पथ विवरण में कुछ वर्ण प्रश्नचिह्न (?) से बदले गए हैं, जो उस स्थान पर दिशा को अज्ञात दिखाते हैं।आपका काम है कि दिए गए पथ विवरण से मेल खाने वाले सभी संभावित पथों की संख्या का पता लगाएँ।
इनपुट
इनपुट की पहली पंक्ति में एक एकल पूर्णांक
n (3 ≤ n ≤ 6) होगा, जो ग्रिड का आकार बताता है।
दूसरी पंक्ति में पथ विवरण दिया गया है, जो L, R, U, D और ? जैसे वर्णों से मिलकर बना हुआ है — जहाँ प्रत्येक वर्ण उस चाल की दिशा दर्शाता है। पथ विवरण की लंबाई के बराबर होती है।आउटपुट
एकल पूर्णांक प्रिंट करें, जो उन सभी विभिन्न पथों की संख्या बताता है जो दिए गए पथ विवरण से मेल खाते हैं।
उदाहरण
इनपुट | आउटपुट |
3
RR??LUL? | 1 |
4
??R??????????L? | 3 |
Constraints
Time limit: 3 seconds
Memory limit: 512 MB
Output limit: 1 MB