問題文

素数 $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\le p\le {10}^6$
• $0\le k\le p-1$
(22:11 制約を追記しました)

出力

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

サンプル

393727 155695

587563550