#P17635. [ICPC 2019 Yinchuan R] Easy Problem
[ICPC 2019 Yinchuan R] Easy Problem
Problem Description
A sequence is -good if and .
Given four integers , , and , you are asked to calculate the sum of for each -good sequence , where $f((a_{1},a_{2},...a_{n}),k) = (a_{1}a_{2} \cdots a_{n})^{k}$ for the sequence .
Since the answer could be very large, you only need to output the answer modulo .
Input Format
The first line is an integer , which is the number of test cases.
For each test case, the first line contains four integers , , , , which are described in the problem description.
Output Format
For each test case, output a line containing a single integer.
1
3 3 3 1
27