Beautiful Sequence
/

## Mathematics, Modular arithmetic, Number Theory

Problem
Editorial
Analytics

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

SAMPLE INPUT
3
5 1
5 2
10 2


SAMPLE OUTPUT
1
2
254

Explanation

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

Time Limit: 2.0 sec(s) for each input file.
Memory Limit: 512 MB
Source Limit: 1024 KB

## This Problem was Asked in

Initializing Code Editor...