Abhimanyu has a complete binary tree of level L, called Crazy Tree. Levels are numbered 1, 2, ..., L from top to bottom and root is at level 1. Abhimanyu numbers all the leaf nodes 1, 2, 3, ... from left to right. The value of the parent node is the product of values of its child node.

Below are level 2 (left) and level 3 (right) crazy trees

Abhimanyu defines a magical function S:

• S(N, X, Y): This gives the sum of X^th, (X + 1)^th, (X + 2)^th, ..., Y^th nodes at level N.

Abhimanyu wants to find the value of S(N, X, Y) % M for given values of N, X, Y, where M = 1299709.

Input

First line of input contains two space separated integers L and Q, where L is number of levels in the crazy tree and Q is total number of queries. Each of the next Q lines contains three space separated integers N, X and Y.

Output

Output the value of S(N, X, Y) % M in single line for each test case.

Constraints

• 1 <= L <= 21
• 1 <= Q <= min(10⁶, (2^L - 1) (2^L + 4) / 6), where min(a, b) is minimum of a and b
• 1 <= N <= L
• 1 <= X <= 2^{(L - 1)}
• X <= Y <= 2^{(L - 1)}