SOLVE
LATER
A sequence is beautiful if the number of times each number appears in that sequence is divisible by \(5\). For example, \((1, 1, 1, 1, 1, 3, 3, 3, 3, 3)\) is beautiful while \((1, 1, 1, 1, 1, 3)\) is not.
You are given \(Q\) queries, each comprises two integers \(N, M\). You must count the number of beautiful sequences of \(N\) integers where each element ranges from \(1\) to \(M\). (Two sequences are different if there exists a position where elements in two sequences are different.)
Input format
Output format
Constraints
\(1 \le Q \le 1000\)
\(1 \le N \le 10^{18}\)
\(1 \le M \le 10^{18}\)
In the first query, there is only one beautiful sequence: \((1, 1, 1, 1, 1)\).
In the second query, there are two beautiful sequences: \((1, 1, 1, 1, 1), (2, 2, 2, 2, 2)\).