Beautiful Sequence
Tag(s):

## Hard, 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
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, TypeScript, Visual Basic

## CODE EDITOR

Initializing Code Editor...

## This Problem was Asked in Challenge Name

HourStorm #5

OTHER PROBLEMS OF THIS CHALLENGE
• Algorithms > Searching
• Data Structures > Advanced Data Structures