Sum of Power of Digit Sum

作問者: loop0919

問題文

「$N$ 以下の桁和が素数である正整数」の $K$ 乗和を $P・Q$ で割った余りを求めよ。

制約

• 入力される値はすべて整数
• $1 \leq N \lt \color{red} 10^{200}$
• $1 \leq K \leq 10$
• $10^8 \leq P \lt Q \leq 10^9$
• $P, Q$ は素数

入力

入力は以下の形式で標準入力から与えられる。

出力

答えを出力せよ。

サンプル

入力例 1

20
2 924844033 998244353

出力例 1

1204

桁和が素数である $20$ 以下の正整数は $2, 3, 5, 7, 11, 12, 14, 16$ です。
これらの $2$ 乗和は $1204$ となります。

入力例 2

314159265358979323846264338327950288419716939937510
10 327441187 987449347

出力例 2

143801804907199008