Bessie has been procrastinating on her cow-mistry homework and now needs your help! She needs to create a mixture of three different cow-michals. As all good cows know though, some cow-michals cannot be mixed with each other or else they will cause an explosion. In particular, two cow-michals with labels a and b can only be present in the same mixture if a⊕b≤K(1≤K≤10^9).

NOTE: Here, a⊕b denotes the "bitwise exclusive or'' of non-negative integers a and b. This operation is equivalent to adding each corresponding pair of bits in base 2 and discarding the carry. For example,

0⊕0=1⊕1=0,

1⊕0=0⊕1=1,

5⊕7=101_2⊕111_2=010_2=2.

Bessie has N(1≤N≤2⋅10^4) boxes of cow-michals and the i-th box contains cow-michals labeled l_i through r_i inclusive (0≤l_i≤r_i≤10^9). No two boxes have any cow-michals in common. She wants to know how many unique mixtures of three different cow-michals she can create. Two mixtures are considered different if there is at least one cow-michal present in one but not the other. Since the answer may be very large, report it modulo 10^9+7.

#5793 upload - done - how_to_reg -

Cowmistry timer 1s memory 512MB

#5793

Cowmistry 1s 512MB