Colorful Grids

All submissions for this problem are available.
You are given five N x N grids, where each grid consists of N^{2} unit squares. These grids have been placed in the form of a plus sign(+). For example, image below shows the figure for N = 2.
Your aim is to count total distinct ways to color all 5*N^{2} unit squares with C colors. Two ways are counted as same if one figure can be rotated in the two dimensional plane to obtain the other one.
Input
The first line of the input contains an integer T denoting the number of test cases. Each test case contains two space separated integers N and C, in one line.
Output
For each test case, output a single line containing the required answer modulo 10^{9} + 7.
Constraints
 1 ≤ T ≤ 10000
 1 ≤ N ≤ 10^{18}
 1 ≤ C ≤ 10^{9}
Example
Input: 2 1 1 1 2 Output: 1 12
Explanation
Example case 1. The only way is to fill all cells with same color.
Example case 2. Assume that the two colors are 1 and 2. The 12 distinct ways are:
2 2 2 2 2 _______ 1 2 2 2 2 _______ 2 2 1 2 2 _______ 2 1 2 1 2 _______ 1 2 2 1 2 _______ 1 2 1 2 2 _______ 1 2 1 2 1 _______ 1 2 1 1 2 _______ 1 2 2 1 1 _______ 1 2 1 1 1 _______ 1 1 2 1 1 _______ 1 1 1 1 1
Author:  admin3 
Tags  admin3 
Date Added:  18102016 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.5 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 