SP21409 GRIDSUM3 - 2x2 Subgrid Sum Problem (generalized)
Description
This problem is a higher constraints and generalized version of [KWACIK](http://pl.spoj.com/problems/KWACIK/) (Polish) and [GRIDSUM2](../GRIDSUM2/).
You are given a **_k_**x**_k_** grid. You can place an integer _m_ (**_a_** m **b**) in each cell.
How many ways are there to place integers in the cells such that the sum of each 2x2 subgrid is _**n**_ ?
Since the answer might be very large, output it modulo **479001600** (= **12!**).
Input Format
The first line contains an integer **_T_** (1 **T**
On each of the next **_T_** lines, you are given four integers **_k_**, _**a**_, **_b_** and _**n**_.
(2 _k_ _a_ _b_ _n_
Output Format
For each test case, output a single line containing the number of ways to place integers modulo **479001600** (= **12!**).