No.2380 Sylow P-subgroup
Problem Statement
Find the order of a Sylow $P$-subgroup of the symmetric group of degree $N$, modulo $998244353$.
(What is the symmetric group of degree $N$?)
It is the group consisting of all bijections on the set $\{1,2,\ldots,N\}$. Its order is $N!$.
(What is a Sylow subgroup?)
Consider a group of order $m$. Let $p$ be a prime, and write $m=p^e\times k$ using a non-negative integer $e$ and a positive integer $k$ that is not a multiple of $p$. Then there exists a subgroup of order $p^e$. Such a subgroup is called a Sylow $p$-subgroup.
Constraints
- $N$ is an integer satisfying $1\le N\le 10^{12}$
- $P$ is a prime satisfying $2\le P\lt 998244353$
Input
$N$ $P$
Output
Output the answer modulo $998244353$.
Sample
Sample 1
Input
4 2
Output
8
The order of the symmetric group of degree $4$ is $4!=24=2^3\times 3$, so the order of a Sylow $2$-subgroup is $2^3=8$.
Sample 2
Input
1 11
Output
1
Sample 3
Input
1000000000000 998244341
Output
506700903
Output the answer modulo $998244353$.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。