Bitmasks are cool. A bitmask is a string of binary bits (0s and 1s). For example: “01010” is a bitmask. Kuldeep is a naughty but brilliant computer scientist. In his free time, he writes some random programs to play with bitmasks. He has a PhD student under him and to test him (and entertain himself), he has given him the following task: Given a number N, write a bitmask of length N containing all 0s. Now, you are given 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).You need to find the sum of all the queries. Note:

- In case there are no queries, return 0.
- As the answer can be large, output the answer mod 1000000007
- Consider 0 based indexing

Constraints:

1 <= N <= 100000

1 <= Q <= 100000

0 <= l, r < N

Input format:

int A: Number N as described above

vector<vector > B: Q operations as described above.

Each row contains three numbers (type, l, r). If type is 0, its an update operation else a query operation.

Example:

Input:

N = 5

Operations: [[0, 1, 3], [1, 1, 2], [0, 0, 4], [1, 3, 4]]

Output:

3

Explanation:

Initial mask: 00000

Operation 1: Update (1,3) , Resulting mask = 01110

Operation 2: Query (1,2), Answer to query = 2

Operation 3: Update (0, 4), Resulting mask = 00001

Operation 4: Query (3,4), Answer to query = 1

Sum of all the queries = 2+1 = 3

Answer = 3%1000000007 = 3

You need to find the sum of all the queries.