Games With Shiva!
Tag(s):

## Medium-Hard, Medium-Hard, mathematics

Problem
Editorial
Analytics

Shiva and Anshul play a game to take a break from programming. Anshul has won W coins in the previous programming contests.So, he puts N of those coins into a stack. Shiva starts first by removing s(0<s<N) coins initially and on alternate turns, each player removes some p number of coins such that p is a divisor of the number of coins removed on previous turn by the other player. The player who can not make a move loses the game. Help Anshul find the largest stack of coins N he should choose from these W coins so that he can certainly win the game.

After losing the previous game, Shiva gets furious and challenges Anshul for another game.

He gives him a M*M board containing M^2 unit squares in which some are colored white and others are colored black. He then asks him to select three squares from the board (A,B,C) such that A,B are in the same row and B,C are in same column. He also puts a condition that A and C should be white and B should be black. The maximum number of ways to select such triplets are Q(for any permutation of white and black).

Print Q*N mod 1000000007.

### INPUT:

First line contains a single integer T denoting the number of test cases. T lines follow, each containing two integers W and M.

### OUTPUT:

Output the answer for each test case in seperate lines.

### CONSTRAINTS:

T <=100

1<=W<=1000000

1<=M<=10000

SAMPLE INPUT
1
2 2
SAMPLE OUTPUT
4
Explanation

In this case, Anshul can select a two coins and can assure a win. So, N=2. Also, Q=2 for 2*2 board.

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

## CODE EDITOR

Initializing Code Editor...

## This Problem was Asked in

Challenge Name

GeekWar

OTHER PROBLEMS OF THIS CHALLENGE
• Math > Probablity