SOLVE

LATER

Strange Creatures

Problem

Editorial

Analytics

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$$**,

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

**Input**

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

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

**Output**

Print the desired Output modulo $$10^9+7$$.

**Constraints**

$$1 \le T \le 1000.$$

$$1 \le A < 100 .$$

$$ 1 \le N \le 10^{18} .$$

Explanation

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++,
Clojure,
C#,
D,
Erlang,
F#,
Go,
Groovy,
Haskell,
Java,
Java 8,
JavaScript(Rhino),
JavaScript(Node.js),
Lisp,
Lisp (SBCL),
Lua,
Objective-C,
OCaml,
Octave,
Pascal,
Perl,
PHP,
Python,
Python 3,
R(RScript),
Racket,
Ruby,
Rust,
Scala,
Scala 2.11.8,
Swift,
Visual Basic

Initializing Code Editor...

{"ca8308e": "/pagelets/suggested-problems/algorithm/strange-creatures/", "ca830d5": "/pagelets/problems-hint/algorithm/strange-creatures/", "ca830fe": "/pagelets/recommended-problems/algorithm/strange-creatures/", "ca83066": "/pagelets/show-submission/algorithm/strange-creatures/", "ca830b3": "/pagelets/problem-author-tester/algorithm/strange-creatures/"}

{}

realtime.hackerearth.com

80

a5300e7e33b83d088c1dcd312f2c79eb01111652

58a29e5cae2309f04b28

/realtime/pusher/auth/