No.1728 [Cherry 3rd Tune] Bullet
Notice (added 2022/07/08)
This problem was used in a contest held on October 29, 2021.Problem Statement
$\mathcal{G}1$ and $\mathcal{G}2$ are almost the same problem, but they differ in constraints and execution time limit.
To commemorate the holding of this contest, Cherry-chan is going to make an objet that satisfies the following.
- $\Gamma_N$ is a regular $N$-gonal prism satisfying the following.
- Each base is a regular $N$-gon with side length $1$.
- Among the edges of the lateral faces, all edges connecting vertices of the two bases have length $2$.
- All lateral faces are perpendicular to the bases.
- For each of the $2N$ vertices of $\Gamma_N$, choose $1$ color from the total of $C$ colors, color $1, \dots,$ color $C$, and paint the vertex with it.
However, making an objet similar to an existing one would cause a backlash on social media. Moreover, even if that is not the case now, if a similar one appears later, she would get caught in the crossfire and things would become troublesome. Concerned about this, Cherry-chan became curious about how many objects she can make under the above conditions. So, given $N, C$, find the answer to the following problem.
- How many ways are there to color the $2N$ vertices of $\Gamma_N$, where colorings that coincide under rotation are not distinguished? Output the remainder when divided by $10^9+7$.
Answer for $T$ test cases.
Constraints
- $1 \leq T \leq 10$
- $3 \leq N \leq 10^9$
- $1 \leq C \leq 10^9$
- All inputs are integers.
Input
Input is given from standard input. Line $1$ of the input has the following format.
$T$Then, $T$ test cases follow. Each test case is given in the following format.
$N$ $C$
Output
Output $T$ lines in total. On line $t~(1 \leq t \leq T)$, output the number of ways to color the $2N$ vertices of $\Gamma_N$ in test case $t$, where colorings that coincide under rotation are not distinguished, modulo $10^9+7$.
Do not forget the newline.
Sample
Sample 1
Input
3 3 2 5 1 46 20211031
Output
16 1 173884620
- [About test case 1] If color $1$ is red and color $2$ is blue, there are the following 16 ways to paint.
- [About test case 2] Since only 1 color can be used, the only way is to paint all vertices with that color, which is 1 way.
- [About test case 3] Note that you must find the remainder when divided by $10^9+7$ (this is the difference from problem $\mathcal{G}1$).
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
Kazun
tatyam
chocorusk