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
- First line: Integer \(Q\) denoting the number of queries
- Each of the \(Q\) following lines: Two space-separated integers \(N, M\)
Output format
- For each query, print the answer to the modulo \(5011\) in a single line.
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)\).
