All Tracks Math Number Theory Problem

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

Best Submission

Similar Problems

Contributors

This Problem was Asked in

Initializing Code Editor...
Notifications
View All Notifications

?