All Tracks Math Number Theory Problem

Beautiful Sequence
Tag(s):

Hard, Math, Modulus 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, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

HackerEarth

Challenge Name

HourStorm #5

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications

?