• محدودیت زمان: ۳ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

استاد پس از انجام فعالیت‌های خسته‌کننده سعی در سرگرم کردن دوستش دارد. بنابراین تصمیم گرفته تا از او تعدادی سوال بپرسد.

در هر سوال، استاد اعداد صحیح $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