Matrix

All submissions for this problem are available.
A matrix doubling operation is defined as creating a new square matrix of size 2*N with the help of square matrix of size N.
The matrix can be doubled as:
M_{2N*2N} = A*M_{N*N} B*M_{N*N} C*M_{N*N} D*M_{N*N}
Where A, B, C, D are integers and M_{i*j} is a matrix of size i * j.
Given a matrix of size 1x1 and two numbers X and Y, find out the element which occurs at the X^{th} row and Y^{th} column location after doubling the matrix to a just sufficient size.
Input
First line will contain T, the number of test cases.
Each test case will consists of three lines.
First line will contain the element present in the 1x1 matrix.
Second line will contain four space separated integers A, B, C, D
Third line will contain two space separated integers, X and Y.
Output
For each test case, output a single integer on a separate line denoting the element at X^{th} row and Y^{th} column.
Constraints
1 ≤ T ≤ 100
The element in the 1x1 matrix will always be 1
0 ≤ A,B,C,D ≤ 9
1 ≤ X,Y ≤ 10^6
Example
Input: 1 1 2 3 4 5 2 7 Output: 36
Explanation
The matrix at various doubling steps will be: 1x1 matrix: 1 2x2 matrix: 2 3 4 5 4x4 matrix: 4 6 6 9 8 10 12 15 8 12 10 15 16 20 20 25 8x8 matrix: 8 12 12 18 12 18 18 27 16 20 24 30 24 30 36 45 16 24 20 30 24 36 30 45 32 40 40 50 48 60 60 75 16 24 24 36 20 30 30 45 32 40 48 60 40 50 60 75 32 48 40 60 40 60 50 75 64 80 80 100 80 100 100 125 Thus the matrix is doubled to a sufficient size and element at the 2nd row and the 7th column is 36
Author:  wittyceaser 
Tags  wittyceaser 
Date Added:  28082014 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions