問題一覧 > 通常問題

No.1177 What's the Remainder?

レベル : / AI推定難易度 : 1600 / 実行時間制限 : 1ケース 1.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 82
作問者 : kozy / テスター : NatsubiSogan
お気に入りにしたユーザー ProblemId : 4758 / 自分の提出
問題文最終更新日: 2021-02-07 23:22:10
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 262 (順位表) の他の問題:

Problem Statement

You are given a prime $p$. (In the given input, the length of the repetend of $\displaystyle \frac{1}{p}$ is $p-1$.)
Also, let $A_1,\ A_2,\ ...,\ A_{p-1} $ be a sequence of integers from $0$ to $9$. (There are ${10}^{p-1}$ possible combinations.)
Find the number of possible tuples $A_1,\ A_2,\ ...,\ A_{p-1}$ such that the remainder of $A_1 + 2 \times A_2 + ... + (p-1) \times A_{p-1}$ divided by $p$ is $k$.
Since the answer can be very large, find the remainder of the answer divided by $10^9+7$.
For more on the "repetend", see also here.

Input

$p$ $k$

  • All inputs are integers.
  • $p$ is a prime such that the length of the repetend of $\displaystyle \frac{1}{p}$ is $p-1$
  • $\displaystyle \frac{1}{p}$ is an infinite decimal
  • $2 \leq p \leq 10^6$
  • $0 \leq k \leq p-1$
  • (22:11 Constraint added)

Output

Output the remainder of the answer divided by $10^9+7$.
Print a newline at the end.

Sample

Sample 1
Input
393727 155695
Output
587563550

Output the remainder of the answer divided by $10^9+7$.

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