Given a number N, write a bitmask of length N containing all 0s. You perform Q operations. Each operation contains two numbers (l, r) as input.

An operation can be one of the following

Update operation: Take the XOR of all the bits in the bitmask from index l to r (both inclusive) with 1.

Query operation: Count the number of set bits in the bitmask between index l to r (both inclusive).

Find the sum of all the queries.

Note

1. As the answer can be large, output the answer mod 1000000007

2. Consider 0 based indexing