Капітан Джек Горобець#12293

Капітан Джек Горобець

1 секунда

256 мегабайтів

Середня

Джек Горобець — один з найвеличніших капітанів. Коли він знайшов новий скарб, він порахував кількість монет. Однак, коли він пізніше перевірив свої монети, він зрозумів, що деякі з них пропали. Джек Горобець — дуже приблизна людина, тому він хоче визначити, скільки монет він втратив.

Він помітив, що для кожного сегмента його подорожі, від $l$ -го кілометра до $r$ -го кілометра, кількість монет, які він втрачає в кожному кілометрі, обчислюється за формулою:

(l & r) + (l \oplus r)

(l\ \&\ r) + (l\ ⊕\ r)

Де $&$ представляє операцію бітового AND, а $\oplus$ представляє операцію бітового XOR.

Джек також знає, що він проходить від $l$ -го кілометра до $r$ -го кілометра, де $a \leq l \leq r \leq b$ a \leq l \leq r \leq b для всіх $l$ і $r$ в різний час.

Тепер капітан хоче знайти кількість втрачених монет. very important ! : answer mod 1e6+3

Формально, обчисліть наступне:

l = a \sum b r = l \sum b ((l \oplus r) + (l & r)) \cdot (r - l)

\displaystyle \sum_{l=a}^b \sum_{r=l}^b ((l \oplus r)+(l \& r)) \cdot (r-l)

Вхідні дані

Перший рядок містить одне ціле число $t$ $(1 \leq t \leq 1 0^{4})$ (1 \le t \leq 10^4) — кількість тестових випадків.

Кожен тестовий випадок містить два цілі числа $a$ , $b$ $(1 \leq a \leq b \leq 1 0^{9}, b - a \leq 2 \cdot 1 0^{5})$ (1 \leq a \leq b \leq 10^{9}, b - a \leq 2\cdot10^5) — межі діапазону.

Гарантується, що $\sum (b - a)$ \sum (b-a) по всіх тестових випадках не перевищує $2 \cdot 1 0^{5}$ 2\cdot10^5.

Вихідні дані

Для кожного тестового випадку виведіть кількість втрачених монет за модулем $1 0^{9} + 7$ 10^9 + 7. very important ! : answer mod 1e6+3

Приклади

Приклад 1

Примітка

У першому тестовому випадку капітан не рухався, тому він не втратив жодної монети.

У другому тестовому випадку капітан проходить ці діапазони:

$[2, 3]$ : Він втратив $(2 & 3) + (2 \oplus 3) = 3$ (2\ \&\ 3) + (2\ \oplus \ 3) = 3 монети за кожен кілометр. Є один кілометр, тому він втратив $3$ монети за цей діапазон.
$[2, 4]$ : Він втратив $(2 & 4) + (2 \oplus 4) = 6$ (2\ \&\ 4) + (2\ \oplus \ 4) = 6 монет за кожен кілометр. Є два кілометри. У першому кілометрі він втратив $6$ монет, а в другому кілометрі він втратив $6$ монет. Отже, він втратив $12$ монет всього за цей діапазон.
$[3, 4]$ : Він втратив $(3 & 4) + (3 \oplus 4) = 7$ (3\ \&\ 4) + (3\ \oplus \ 4) = 7 монет за кожен кілометр. Є один кілометр, тому він втратив $7$ монет за цей діапазон.

Врешті-решт, капітан втратив $3 + 12 + 7 = 22$ 3 + 12 + 7 = 22 монети.

Оцінювання

Підзадача $1$ ( $20$ балів) : $(1 \leq a \leq b \leq 40)$ (1 \le a \le b \le 40)
Підзадача $2$ ( $30$ балів) : $(1 \leq \sum (b - a) \leq 1000)$ (1 \le \sum (b-a) \le 1000)
Підзадача $3$ ( $200$ балів) : Без додаткових обмежень