All submissions for this problem are available.
Sumo was travelling alone at night, suddenly he saw a spaceship and out of it came an alien named KK. Obviously, the alien had a different language and thus couldn't communicate readily. After some psycho-telepathic talk, Sumo realised that KK's language has M distinct characters. And a valid word in his language satisfies the following properties:
- Each character in the word must be one of the M characters. There must be no palindromic substring of size greater than 1.
For some reason Sumo wants to know the number of valid words of length N in KK's language. Since the answer can be large, print the answer modulo 1000000007 (10^9 + 7).
- The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
- The first line of each test case contains two space separated integers N and M as described in the problem statement.
For each test case, output a single line containing the answer to the corresponding test case. See example section for better understanding.
- 1 ≤ T ≤ 100000
- 1 ≤ N ≤ 1000000000
- 1 ≤ M ≤ 1000000000
Input: 2 3 3 1 4 Output: 6 4
|Tags||iitkp2p02, mpc2, triveni|
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, PYP3, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.