完全順列数 $D_n$ は、$1, 2, \dots, n$ の順列 $p$ のうち、すべての $i$ に対して $p_i \neq i$ を満たすものの個数を表します。
ヒント：完全順列数を計算するための単純な漸化式 $D_n = (n-1)(D_{n-1}+D_{n-2})$ が存在します。
小艾（Xiao Ai）は $D_n$ を正確に計算し、その十進法表記を印刷しました。
しかし、プリンターの故障により、ごく一部の数字が読み取れなくなってしまいました。
彼女はあなたに、この欠損した部分の本来の数字を復元してほしいと頼みました。
入力
1行目に正整数 $n$ が与えられます。
続く行に文字列が与えられます。この文字列は数字と疑問符 ? から構成されます。$D_n$ を十進法で表記した文字列を $S$（先頭にゼロはつかない）とします。入力された文字列は、$S$ のある空でない区間が同じ長さの ? に置き換えられたものであることが保証されています。
出力
$D_n$ の正確な値を整数で出力してください。
入出力例
入力 1
10 133??61
出力 1
1334961
小課題
? の合計の長さを $l$ とします。
すべてのテストケースにおいて、$2\le n\le 10^5, 1\le l\le 9$ を満たします。
| テストケース番号 | 特殊な制約 |
|---|---|
| $1, 2$ | $n\le 10$ |
| $3\sim 8$ | $n\le 10^3$ |
| $9\sim 11$ | ? が $S$ の接頭辞を構成する |
| $12\sim 14$ | ? が $S$ の接尾辞を構成する |
| $15\sim 17$ | $l=1$ |
| $18\sim 20$ | なし |