No.3273 Exactly One Match
Problem Statement
You are given positive integers $N,K$. There are $(NK)^N$ possible pairs of a sequence $A = (A_1, A_2, \dots, A_N)$ of length $N$ consisting of integers between $1$ and $N$, inclusive, and a sequence $C = (C_1, C_2, \dots, C_N)$ of length $N$ consisting of integers between $1$ and $K$, inclusive. Find the number, modulo $998244353$, of such pairs that satisfy the following condition.
- There exists exactly one integer $i$ between $1$ and $N$, inclusive, such that $C_i = C_{A_i}$.
Input
$N\ K$
- All input values are integers.
- $1 \le N \le 10^6$
- $1 \le K \le 10^{18}$
Output
Output the number, modulo $998244353$, of pairs of $A$ and $C$ that satisfy the condition.
Sample
Sample 1
Input
2 3
Output
12
The following $12$ pairs of $A$ and $C$ satisfy the condition.
- $A = (1,1), C = (1,2)$
- $A = (1,1), C = (1,3)$
- $A = (1,1), C = (2,1)$
- $A = (1,1), C = (2,3)$
- $A = (1,1), C = (3,1)$
- $A = (1,1), C = (3,2)$
- $A = (2,2), C = (1,2)$
- $A = (2,2), C = (1,3)$
- $A = (2,2), C = (2,1)$
- $A = (2,2), C = (2,3)$
- $A = (2,2), C = (3,1)$
- $A = (2,2), C = (3,2)$
Sample 2
Input
271 828
Output
516955559
Output the answer modulo $998244353$.
Sample 3
Input
1000000 1839286755214161
Output
130737125
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
apricity