All Tracks Math Number Theory Problem

Strange Creatures



Rohan is a great astronaut and a scientist. He lands in a Strange Planet. After searching the planet for days, he notices something strange. He thinks that this might be the sign of life. He sees that, small creatures keep on increasing in pits. These creatures can form new creatures among themselves. He gets very scared when he notices that the Pits keeps increasing too! He goes back to his spaceship and sits down with a pen and a paper to analyze the data so collected. Rohan gets to know by his mathematical abilities that the number of pits at any hour N is \( A^N\), where ‘A’ is the number of creatures in the pit (all pits have the same number of creatures) at the 0th hour.

He finds that it takes \(A^N\) creatures to produce a new creature. And the creature does not reproduce with those creatures in their own pit. One creature can only reproduce when all the other creatures are from another pit .

Rohan messaged this fact to his base on Earth. He wants to know the number of ways in which a new creature can be produced. You being his friend and his colleague, have to give him the number of ways in which a new creature can be produced from the existing creatures. As the number can be very large. So print the number modulo \(10^9+7\).


First Input Line contains T, the number of test cases.

Second Input line contains two space separated integers A and N .


Print the desired Output modulo \(10^9+7\).


\(1 \le T \le 1000.\)

\(1 \le A < 100 .\)

\( 1 \le N \le 10^{18} .\)

2 3

For TestCase 1 (T=1).

Number of creatures in each pit=2

Number of pits at the hour 3 = \(2^3\) = 8.

So, the number of ways of selecting 8 creatures from 8 pits to reproduce
= \(^2P_1* ^2P_1* ^2P_1* ^2P_1* ^2P_1* ^2P_1* ^2P_1* ^2P_1=256\).

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: 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, Visual Basic


Initializing Code Editor...
Your Rating:


View All Notifications