题目背景

$\small\color{white}54^{\text{th}}\text{Problem by ArCu}.$

题目描述

对于 $n\times n$ 矩阵 $A$，定义 $f(A)$ 为最小的满足 $A^b=O$ 的正整数 $b$，若不存在这样的数则 $f(A)=0$。其中 $O$ 是零矩阵，即所有元素都是 $0$ 的矩阵。

给定 $n,a$，每个元素都是 $[0,a)$ 中整数的 $n\times n$ 矩阵有 $a^{n^2}$ 种。对所有 $a^{n^2}$ 种可能的矩阵 $A$ 求 $f(A)$ 之和。

答案对 $202407031$ 取模。

输入格式

一行两个整数 $n,a(1\leq n\leq 600,0<a<2^{64})$。

输出格式

一行一个整数，表示你求得的答案。

2 2

5

3 4

793

5 10

59350891

18 15932416

52138206

1 1

1

提示

$\text{Sample 1 Explanation}:$

注意到对于任意正整数 $b$，$\begin{bmatrix}1&0\\1&1\end{bmatrix}^b\neq O$，所以 $f\left(\begin{bmatrix}1&0\\1&1\end{bmatrix}\right)=0$。而 $\begin{bmatrix}0&0\\1&0\end{bmatrix}^2=O$，所以 $f\left(\begin{bmatrix}0&0\\1&0\end{bmatrix}\right)=2$。

一共有 $2^4=16$ 种可能的矩阵。其中 $f(A)$ 不为 $0$ 的只有

$$f\left(\begin{bmatrix}0&0\\0&0\end{bmatrix}\right)=1,f\left(\begin{bmatrix}0&0\\1&0\end{bmatrix}\right)=f\left(\begin{bmatrix}0&1\\0&0\end{bmatrix}\right)=2 $$

答案即为 $1+2+2=5$。

$\text{Details of Subtasks}:$

所有数据满足 $1\leq n\leq 600,0<a<2^{64}$。

$\text{Subtask}$	$\text{Special Constraints}$	$\text{Score}$
$1$	$n\leq 5,a\leq 2$	$3$
$2$	$n\leq 5$	$7$
$3$	$n\leq 10$	$10$
$4$	$n\leq 40$	$20$
$5$	$n\leq 200$	$30$
$6$

$\text{Hint}:202407031=13009\times 15559.$