- محدودیت زمان: ۳ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت
استاد پس از انجام فعالیتهای خستهکننده سعی در سرگرم کردن دوستش دارد. بنابراین تصمیم گرفته تا از او تعدادی سوال بپرسد.
در هر سوال، استاد اعداد صحیح \(l\)، \(r\) (\(l \le r\)) و \(x\) را به دوستش میدهد و از او میخواهد تا تعداد سابنامانیهای آرایهی \([l \oplus x, (l+1) \oplus x, (l+2) \oplus x, \dots, r \oplus x]\) را به پیمانه \(10^9+7\) پیدا کند.
در آرایهی \([a_1, a_2, \dots, a_n]\) زوج \(1 \le i, j \le n\) یک سابنامانی تشکیل میدهند هرگاه \(i < j\) و \(a_i > a_j\). تعداد سابنامانیهای آرایه برابر تعداد زوجهایی است که تشکیل سابنامانی میدهند.
در اینجا \(\oplus\) نشاندهندهی یای انحصاری است.
ورودی
در خط اول ورودی عدد صحیح \(t\) که برابر تعداد سوالهای استاد است میآید. \[1 \le t \le 100,000\]
در هر یک از \(t\) خط بعدی، سه عدد \(l\)، \(r\) و \(x\) که مشخصات سوال استاد هستند میآیند.
\[0 \le l, r, x \le 10^{18} \quad l \le r\]
خروجی
برای هر سوال استاد، در یک خط پاسخ را به پیمانه \(10^9+7\) خروجی دهید.
مثال
ورودی نمونه ۱
3
1 4 2
1234 5678 91011
121314151617181920 212223242526272829 303132333435363738
خروجی نمونه ۱
2
1786376
904814375
ارسال پاسخ برای این سؤال