パスの説明

n x n のグリッドが与えられています。パスはセル (1, 1) から始まり、すべてのセルを一度ずつ訪問しながら、最終的にセル (n, 1) で終了します。パスの移動は右 (R)、左 (L)、上 (U)、下 (D) の4方向だけで、それぞれのセルには最大1回しか入れません。パスの内容は文字列 LRUD で表されますが、いくつかの文字が ? に置き換えられており、その部分の移動方向は不明とされています。

このとき、与えられたパス記述に合致する経路がいくつあるかを求めるのが課題です。

入力

1行目にはグリッドのサイズを表す整数 n (3 ≤ n ≤ 6) が与えられます。

出力

与えられたパス記述に合致する異なるパスの数を、1つの整数として出力してください。

例