Alice, who was exploring ruins in search of treasure, arrived at a corridor where the entrances to rooms were lined up in a row. Upon investigation, she found that the rooms were numbered uniquely from to , but the exact number of each room was unknown until she entered. She discovered that the treasure was hidden in room .
Given her remaining stamina, it was difficult for Alice to check all the rooms. However, Alice had a secret strategy to overcome this situation: binary search. Alice had successfully applied binary search to various challenges before. With her last ounce of strength, she decided to use binary search to find room .
Specifically, she followed these steps:
Initialize variables and with and .
Repeat steps 1 to 3 as follows:
If , stop the operation as she has not found room .
Set . Enter the room positioned -th from the left, check its number, and let this number be .
If , stop the operation as she has found room . If , update to . If , update to .
There are possible mappings between rooms and numbers. You need to determine the number of mappings for which Alice can successfully find room using the above procedure, modulo .
Given test cases, compute the answer for each.
输入格式
The input is given in the following format:
Here, denotes the -th test case.
Each test case is given in the following format:
All input values are integers.
输出格式
Output lines. On the -th line, output the answer for the -th test case.
