Abhimanyu makes a complete binary tree of level L, called Crazy Tree. The levels are numbered 1, 2, ..., L from top to bottom. The root of the tree is at level 1. He numbers all the leaf nodes 1, 2, 3, ... from left to right. The value of every parent node is the product of values of its child nodes.
Below are Level 2 (left) and Level 3 (right) Crazy Trees.
Abhimanyu has a magical function S:
For two magical integers X and Y, Abhimanyu wants to find the value of W % M, where:
Input
First line of input contains two space separated integers L and Q, where L is the number of levels in Crazy Tree and Q is number of queries. Each of next Q lines contains two space separated integers X and Y.
Output
Output W % M, for each test case in single line.
Constraints
The tree is Level 3 tree. So, S(1) = 24 S(2) = 14 S(3) = 10