Long Secret Number

2 secs 1024 MB
sgsw

問題文


ABC201-Cと同じ設定を考えます。初めに文字列が与えられるとこまでは同じです。

しかし、4桁ではなく桁の場合はどうなるでしょうか。その場合の答えをで割ったあまりで求めてください。

入力


制約


は同上

・(extra : )

サンプル


入力1
ooo???xxxx 4
出力1
108

これは元々の問題のサンプル1です。

入力2
o?oo?oxoxo 4
出力2
0

これは元々の問題のサンプル2です。

入力3
xxxxx?xxxo 4
出力3
15

これは元々の問題のサンプル3です。

入力4
ooo???xxxx 1000
出力4
844143439

の場合です。

extra入力1
ooo???xxxx 1000000000000000000
extra出力1
375520645

これはこの問題の制約を満たしませんが、でも解くことができます。

Submit


Go (1.14)