問題一覧 > 通常問題

No.1177 余りは?

レベル : / 実行時間制限 : 1ケース 1.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 79
作問者 : kozykozy / テスター : NatsubiSoganNatsubiSogan
20 ProblemId : 4758 / 出題時の順位表
問題文最終更新日: 2021-02-07 23:22:10

問題文

素数 $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$ で割った余りを出力せよ。
最後に改行すること。

サンプル

サンプル1
入力
393727 155695
出力
587563550

答えを $10^9+7$ で割った余りを出力せよ。

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