問題一覧 > 通常問題

No.372 It's automatic

レベル : / 実行時間制限 : 1ケース 6.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 86
作問者 : koba-e964 / テスター : 🍡yurahuna
2 ProblemId : 598 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2018-03-10 02:20:43

Note

注意: 想定解はC++で実装されており、最悪ケースで1秒～2秒程度かかります(制限時間は6秒)。他の言語で実装した場合時間切れになる可能性が高いです。
Javaでは3667msです。
テスター解のPython(PyPy)ではTLEになります。

問題文

'0'から'9'までの文字からなる文字Sと、正の整数Mが与えられます。
1文字以上の部分列であって10進数として解釈したものがMの倍数となるようなものの総数をmod 1,000,000,007=109+7で出力してください。
ここで、文字列Sの部分列とは、
1≤a1<a2<⋯<ak≤|S|
なる(ai)iを用いてS[a1]S[a2]⋯S[ak]と表せる文字列のことです。(S[i]はSのi番目の文字)
位置が異なり文字列としては同じ部分列は異なるものとして扱います。例えばS="110"の場合、 1文字目と3文字目からなる部分列"10"と 2文字目と3文字目からなる部分列"10"は別々に数えます。
また、部分列が2文字以上の場合は0から始まるものは数えません。例えばS="02",M=2の場合、"02"は2の倍数とはみなしません。

入力

S
M

1≤|S|≤10,000
1≤M≤20,000
Sの各文字は'0'から'9'である。
サンプルケースのうちファイル名が"testcase-small1-"で始まるものは、1≤|S|≤16,1≤M≤1,000を満たす。
サンプルケースのうちファイル名が"testcase-small2-"で始まるものは、1≤|S|≤10,000,1≤M≤1,000を満たす。

出力

結果を出力してください。 最後に改行してください。

サンプル

サンプル1
入力
012
3
出力
2

0,12の2種類存在します。012は0から始まり2文字以上なので数えません。

サンプル2
入力
220
2
出力
7

2(1文字目), 2(2文字目), 0, 22, 20(1文字目と3文字目), 20(2文字目と3文字目), 220の7種類存在します。

サンプル3
入力
123456789123456789
1
出力
262143

262143=218−1です。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。