No.1177 What's the Remainder?
タグ : / 解いたユーザー数 82
作問者 :
kozy
/ テスター :
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もしくは右上の雲マークをクリックしてアカウントを作成してください。