問題文

素数 $p$ が与えられる。(与えられる入力において、$\displaystyle \frac{1}{p}$ の循環節の長さは $p-1$ である。)
また、$A_1,\ A_2,\ ...,\ A_{p-1} $ を $0$ から $9$ の整数からなる数列とする。（${10}^{p-1}$ 通りの組み合わせが考えられる。）
このとき、$A_1 + 2 \times A_2 + ... + (p-1) \times A_{p-1}$ を $p$ で割った余りが $k$ となる $A_1,\ A_2,\ ...,\ A_{p-1}$ として考えられる組の個数を答えよ。
ただし、答えはとても大きな数になる可能性があるので、答えを $10^9+7$ で割った余りを求めよ。
なお、「循環節」については、こちらも参考にしてください。

入力

$p$ $k$

• 入力はすべて整数
• $p$ は $\displaystyle \frac{1}{p}$ の循環節の長さが $p-1$ となる素数
• $\displaystyle \frac{1}{p}$ は無限小数
• $2 \leq p \leq 10^6$
• $0 \leq k \leq p-1$
(22:11 制約を追記しました)

出力

答えを $10^9+7$ で割った余りを出力せよ。
最後に改行すること。

サンプル

393727 155695

587563550