Why does YahAHa always like cubes?
YahAHa has a special cube. Each side of cube has a number x (1≤x≤1000). At the beginning, YahaHa placed the cube on the table. Then rolled the cube n(1≤n≤2×105 ) times, each time along one edge of bottom side.It means rotate top face to other faces.
YahAHa have a number xx,is 1 in the beginning.After each roll, YahAHa multiply the number on the front side of the cube to xx. The product was so large that YahAHa write down the product module 998244353.
Carelessly, YahAHa forgot m(1≤m≤20) of these rolling directions. But YahAHa has written down the start state of the cube, the final state, and the product of numbers on the front side after module.
Can you tell YahAHa that how many different ways of rolling that satisfy all the conditions?
Each test contains multiple test cases. The first line contains the number of test cases (1≤T≤10). Desc
The first line of the input contains only one integers n(1≤n≤2×105) indicating the number of rolls of the cube.
The next line contains n integers. The ii-th integer (0≤ai≤4) indicating the i-th roll. ai=1 means rotate top face to front; ai=2 means rotate top face to back; ai=3 means rotate top face to left; ai=4 means rotate top face to right; ai=0 means YahAHa has forgotten the direction of this roll;
The next line contains 66 distinct integers indicating the start state of the cube.
The next line contains 66 distinct integers indicating the final state of the cube.
The state of the cube is represented as 6 integers. The 6 integers are sorted by front, back, left, right, top and bottom sides.
The last line contains one integer indicating the product of numbers on the front side module 998244353998244353.
It's guaranteed that there are at most 5 cases such that n≥105,m≥20 .
For each test case:
Print one interger in one line indicating the answer.
1
7
3 0 4 2 0 4 4
1 6 2 3 4 5
1 6 4 5 3 2
31