Centeur

The aliens in Centaurus a star reach the earth on Dec. 21th in 2012, and they are fairly smart. Before creating a friendly relationship with the human beings, they make a request that the intelligence of human must be tested. Upon their will, an earth citizen is asked to play the testing game with their boss, and rules of the game are as follows:
Given a row of bulbs whose total number is n, and the bulbs are numbered 1 to n from left to right, and each bulb has two states, named turned-on and turned-off. With the citizen from earth starts first, two players make their operations by turns. Every operation they make must meet the conditions:
Choose a bulb which is now on, then turn it off, and we assume this bulb is numbered p;
Choose a bulb and change its state(if on, then turn off, else, turn on), and suppose it is numbered q, which should meet the request of q <= p/2.

In addition, the step 2 is not a must.
And the one cannot move loses.
Eventually, the smart earth citizen wins this test soon.

However, another question is asked by an evil alien: Supposing there are turned-on bulbs in some sections at the beginning, and the other states can be decided by the citizen from earth. With this fixed rules, and the alien goes first, then how many original states will make the citizen from earth win the game?

Line 1: a single integer t(1<=t<=30), which refers to the number of cases;
And for each case, the first line contains two integers n m(1<=n<=2⁶³-1,0<=m<=1000), and in the following m lines, each line has two integers:s t(1<=s<=t<=n), which means that the bulbs numbered from s to t (include s and t)are turned-on originally;
Attention, these sections may be overlapped.

For each test case, output a single line with an integer indicates the total original number of states mod 100000007

2
1 1
1 1
3 0

0
2

  When n = 3 , m = 0, there are two kinds of original states guaranteeing the winner of the earth
  citizen (From left to right, the bulbs are numbered 1 to n, and o refers to the turned-on bulbs,
  And * refers to the turned-off):
***
ooo

hust[等待]

ACM-DIY Group Contest 2011 Spring