Kapitan Cek Sparrow#12293

Kapitan Cek Sparrow

1 saniyə

256 meqabayt

Orta

Cek Sparrow ən böyük kapitanlardan biridir. O, yeni bir xəzinə tapdıqda, pul sayını hesablayır. Lakin, daha sonra pullarını yoxlamağa gedəndə, bəzilərinin itkin olduğunu başa düşdü. Cek Sparrow çox dəqiq bir insandır, buna görə də itirdiyi pul sayını müəyyən etmək istəyir.

O, səyahətinin hər bir seqmenti üçün, $l$ -ci kilometrdən $r$ -ci kilometrə qədər, itirdiyi pul sayının hər kilometr üçün aşağıdakı kimi hesablandığını qeyd etdi:

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

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

Burada $&$ bitwise AND əməliyyatını, $\oplus$ isə bitwise XOR əməliyyatını təmsil edir.

Cek həmçinin $a \leq l \leq r \leq b$ a \leq l \leq r \leq b şərti ilə $l$ -ci kilometrdən $r$ -ci kilometrə qədər səyahət etdiyini bilir, burada $l$ və $r$ fərqli zamanlardadır. very important ! : answer mod 1e6+3

İndi kapitan itirdiyi pul sayını tapmaq istəyir.

Rəsmi olaraq, aşağıdakıları hesablayın:

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)

Giriş

İlk sətirdə bir tam ədəd $t$ $(1 \leq t \leq 1 0^{4})$ (1 \le t \leq 10^4) — test halları sayını göstərir.

Hər test halı iki tam ədəd $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) — aralığın sərhədlərini ehtiva edir.

Bütün test hallarının $\sum (b - a)$ \sum (b-a) cəminin $2 \cdot 1 0^{5}$ 2\cdot10^5-dən çox olmayacağına zəmanət verilir.

Çıxış

Hər test halı üçün, itirilmiş pul sayını $1 0^{9} + 7$ 10^9 + 7 modulunda çap edin. very important ! : answer mod 1e6+3

Nümunələr

Nümunə 1

Qeyd

Birinci test halında, kapitan hərəkət etmədi, buna görə də heç bir pul itirmədi.

İkinci test halında, kapitan bu aralıqları keçdi:

$[2, 3]$ : O, hər kilometr üçün $(2 & 3) + (2 \oplus 3) = 3$ (2\ \&\ 3) + (2\ \oplus \ 3) = 3 pul itirdi. Bir kilometr var, buna görə də bu aralıq üçün $3$ pul itirdi.
$[2, 4]$ : O, hər kilometr üçün $(2 & 4) + (2 \oplus 4) = 6$ (2\ \&\ 4) + (2\ \oplus \ 4) = 6 pul itirdi. İki kilometr var. Birinci kilometrdə $6$ pul itirdi, ikinci kilometrdə isə $6$ pul itirdi. Beləliklə, bu aralıq üçün cəmi $12$ pul itirdi.
$[3, 4]$ : O, hər kilometr üçün $(3 & 4) + (3 \oplus 4) = 7$ (3\ \&\ 4) + (3\ \oplus \ 4) = 7 pul itirdi. Bir kilometr var, buna görə də bu aralıq üçün $7$ pul itirdi.

Nəticədə, kapitan $3 + 12 + 7 = 22$ 3 + 12 + 7 = 22 pul itirdi.

Bal hesablama

Alt tapşırıq $1$ ( $20$ xal) : $(1 \leq a \leq b \leq 40)$ (1 \le a \le b \le 40)
Alt tapşırıq $2$ ( $30$ xal) : $(1 \leq \sum (b - a) \leq 1000)$ (1 \le \sum (b-a) \le 1000)
Alt tapşırıq $3$ ( $200$ xal) : Əlavə məhdudiyyət yoxdur