Farewell Gift for Messi

Lionel Messi, the greatest footballer of all time, is going to retire from international football! On Messi’s retirement announcement ceremony, his teammates Emiliano Martínez and Rodrigo De Paul decided to gift Messi an array of $n$ non-negative integers where each element of the array is strictly less than $2^p$. Martínez will be happy if the bitwise OR of all elements of the array is equal to $x$. On the other hand, De Paul will be happy if the bitwise AND of all elements of the array is equal to $y$.

You have to find the number of possible arrays for which both Martínez and De Paul will be happy to gift it to Messi. Since the number may be very large, print it modulo Messi’s favorite number $998244353$.

Input

First line of input is a single integer $T$ ($1 \le T \le 1500$) denoting number of test cases.

Each of the next $T$ lines describes the input for a single test case which consists of four integers: $n$ ($1 \le n \le 50$), $p$ ($1 \le p \le 30$), $x$ ($0 \le x < 2^p$) and $y$ ($0 \le y < 2^p$).

Output

For each test case, output the number of arrays which satisfies all the conditions stated above. Since the number may be very large, print it modulo $998244353$.

Sample

Input	Output
3 3 1 1 0 2 4 11 8 21 12 4044 3980	6 4 2097150
Possible arrays for test 1:$[1,1,0], [1,0,1], [0,1,1], [0,0,1], [0,1,0], [1,0,0]$ Possible arrays for test 2: $[8,11], [9,10], [10,9], [11,8]$