背景

$12$ 月 $11$ 日は "International Mountain Day" - これは山の日の国際版であるので、これに関して問題を出す。

問題文

あなたはある山岳地帯のツアーを企画しようとしている. この山岳地帯は南北方向に $H$ マイル, 東西方向に $W$ マイルの長方形の形をしている. また, 区画 $(i, j)$ を, 北から $i$ マイル ～ $i+1$ マイル, 西から $j$ マイル ～ $j+1$ マイルの位置にある部分とする.
あなたは次の条件で, ツアーのルートを決めたい.

• スタート地点を駐車場のある区画 $(1, 1)$, ゴール地点を山頂のある区画 $(H, W)$ にする.
• ツアー中に遭難するのをできるだけ避けたいので, 東方向に $1$ 区画, あるいは南方向に $1$ 区画の移動を何回か行うことでスタートからゴールまで移動することにする.
• ツアーにかかる時間は (通ったマスの「歩きにくさ (1以上9以下の整数)」の合計としてありうる値の中で最小の値) である.

1. 歩きにくさがまだ分かっていないマスの歩きにくさを全部 $1$ にした場合のツアーにかかる時間 $T$ (時間)
2. ツアーにかかる時間が $T$ 時間であるような, マップ (歩きにくさの割り当て方) の種類数 $X$

入力

• $1$ 行目には, 整数 $H$ と $W$ が与えられる.
• $i+1$ 行目には, 文字列 $A_i$ が与えられる. $A_i$ の $j$ 文字目が $1$ 以上 $9$ 以下の数字のときこれは区画 $(i, j)$ の歩きにくさの値を表し, '?' のとき区画 $(i, j)$ の歩きにくさがまだ分かっていないことを表す.

出力

• $1$ 行目に $T$ の値を出力せよ.
• $2$ 行目に $X$ を $201{,}712{,}111$ で割った余りを出力せよ.

制限

• $4HW \leq 1211$.
• $A_i \ (1 \leq i \leq H)$ は '1' ～ '9' または '?' のみで構成されている $W$ 文字の文字列である.

サンプル

3 4
1111
????
1111

6
2465

3 4
3333
????
3333

10
1

3333
1111
3333

6 6
2?17??
?1211?
??2?17
1211??
?2?17?
??1211

13
24869728