+ محدودیت زمان: ۳ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- استاد پس از انجام فعالیت‌های خسته‌کننده سعی در سرگرم کردن دوستش دارد. بنابراین تصمیم گرفته تا از او تعدادی سوال بپرسد. در هر سوال، استاد اعداد صحیح $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$ نشان‌دهنده‌ی [یای انحصاری](https://fa.wikipedia.org/wiki/%DB%8C%D8%A7%DB%8C_%D8%A7%D9%86%D8%AD%D8%B5%D8%A7%D8%B1%DB%8C) است. # ورودی در خط اول ورودی عدد صحیح $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 ```