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 non-negative integers where each element of the array is strictly less than . Martínez will be happy if the bitwise OR of all elements of the array is equal to . On the other hand, De Paul will be happy if the bitwise AND of all elements of the array is equal to .
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 .
First line of input is a single integer () denoting number of test cases.
Each of the next lines describes the input for a single test case which consists of four integers: (), (), () and ().
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 .
Input | Output |
---|---|
3 3 1 1 0 2 4 11 8 21 12 4044 3980 | 6 4 2097150 |
Possible arrays for test 1: Possible arrays for test 2: |