Ճանապարհի նկարագրություն
Ձեզ տրված է
n x n չափի բջիջների ցանց։ Ուղին սկսվում է (1, 1) բջջից, անցնում է ցանցի բոլոր բջիջներով և ավարտվում է (n, 1) բջջում։ Այն կարող է շարժվել միայն աջ (R), ձախ (L), վեր (U) կամ վար (D), ընդ որում յուրաքանչյուր բջիջ թույլատրելի է գնալ միայն մեկ անգամ։ Ուղու նկարագրությունը տրված է LRUD նշանների միջոցով, որտեղ յուրաքանչյուր նշանը ցույց է տալիս համապատասխան շարժման ուղղությունը։Սակայն ուղու նկարագրության մեջ որոշ նշաններ փոխարինված են հարցական նշանով (
?), ինչը նշանակում է, որ տվյալ քայլի ուղղությունը հայտնի չէ։Մուտք
Մուտքիแรก տողում տրված է մեկ ամբողջ թիվ
n (3 ≤ n ≤ 6), որը ցույց է տալիս ցանցի չափը։Ելք
Պետք է տպել մեկ ամբողջ թիվ, որը ցույց է տալիս, թե քանի տարբեր ուղիներ են բավարարում տրված ուղու նկարագրությանը։
Օրինակներ
Մուտք | Ելք |
3
RR??LUL? | 1 |
4
??R??????????L? | 3 |
Constraints
Time limit: 3 seconds
Memory limit: 512 MB
Output limit: 1 MB