Background

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

Problem Description

For an $n \times n$ matrix $A$, define $f(A)$ as the smallest positive integer $b$ such that $A^b = O$. If no such integer exists, then $f(A)=0$. Here $O$ is the zero matrix, i.e. the matrix whose all entries are $0$.

Given $n,a$, there are $a^{n^2}$ different $n \times n$ matrices whose every entry is an integer in $[0,a)$. Compute the sum of $f(A)$ over all these $a^{n^2}$ possible matrices $A$.

Output the answer modulo $202407031$.

Input Format

One line with two integers $n,a(1\leq n\leq 600,0<a<2^{64})$.

Output Format

One line with one integer, representing the answer you computed.

2 2

5

3 4

793

5 10

59350891

18 15932416

52138206

1 1

1

Hint

$\text{Sample 1 Explanation}:$

Note that for any positive integer $b$, $\begin{bmatrix}1&0\\1&1\end{bmatrix}^b\neq O$, so $f\left(\begin{bmatrix}1&0\\1&1\end{bmatrix}\right)=0$. Also, $\begin{bmatrix}0&0\\1&0\end{bmatrix}^2=O$, so $f\left(\begin{bmatrix}0&0\\1&0\end{bmatrix}\right)=2$.

There are $2^4=16$ possible matrices in total. The only ones with $f(A)\neq 0$ are

$$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$$

So the answer is $1+2+2=5$.

$\text{Details of Subtasks}:$

All testdata satisfy $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.$

Translated by ChatGPT 5