crystals are aligned in a row. However, some of them may be phantoms.
Jun counted the number of real crystals from -th to -th (closed interval) for every pair and recorded their evenness.
His records show that there were intervals that contained an odd number of real crystals. How many possible crystal alignments are there? Answer the remainder divided by .
Note that if there is such that the -th crystal from the left is real on one side and phantom on the other, the two alignments are considered different.
You are given of the above problems. Answer each of them.
输入格式
The input satisfies the following constraints.
All inputs consist of integers.
输出格式
Output lines. On the line , answer the problem when . Add a new line at the end of each line.
样例
样例输入 1
1
3 4
样例输出 1
3
样例输入 2
5
5 9
6 10
10 24
10 25
100000 75915540
样例输出 2
10
21
165
0
651081880
数据范围与提示
If we denote a real crystal as and an phantom as , the following three alignments satisfy the condition at Sample Input 1.
