Safe Chemical Mixtures

Bessie has been procrastinating her chemistry homework for a long time and now needs your help! She must produce a mixture using three different chemicals selected from her collection. There are multiple boxes and the i-th box contains chemicals labeled from l_i to r_i (with 0 ≤ l_i ≤ r_i ≤ 10⁹). No chemical appears in more than one box.

However, not every pair of chemicals can be mixed safely. Two chemicals with labels a and b can appear in the same mixture if and only if

[ a \oplus b \le K ]

where K is an integer (1 ≤ K ≤ 10⁹) and \(a \oplus b\) denotes the bitwise XOR of a and b. Recall that the XOR operation is performed on the binary representations of a and b and is defined bitwise as:

[ 0 \oplus 0 = 1 \oplus 1 = 0, \quad 1 \oplus 0 = 0 \oplus 1 = 1, ]

For example:

[ 5 \oplus 7 = 101_2 \oplus 111_2 = 010_2 = 2. ]

Your task is to count the number of distinct mixtures that Bessie can create using three different chemicals such that for every pair (a, b) chosen from the mixture, the condition a \oplus b ≤ K holds. Two mixtures are considered different if there exists at least one chemical that is present in one mixture and not in the other. Since the answer might be very large, output it modulo 10⁹+7.

inputFormat

The first line contains two integers N and K, where N is the number of boxes and K is the XOR threshold.

Each of the following N lines contains two integers l_i and r_i representing that the i-th box contains all chemicals with labels from l_i to r_i (inclusive). It is guaranteed that no chemical appears in more than one box.

outputFormat

Output a single integer representing the number of valid mixtures (three-chemical selections) meeting the safety condition, taken modulo 10⁹+7.

sample

1 1
1 3

0