• محدودیت زمان: ۲ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت
• منبع: آزمون مقدماتی اول دوره ۲۶ المپیاد کامپیوتر

---

توابع \(f: \mathbb{N} \rightarrow \{-1, 1\}\) و \(g: \mathbb{N} \rightarrow \mathbb{Z}\) به صورت زیر تعریف می‌شوند:

\[g(n)=\sum_{i=1}^{n}f(i)\]

در توضیحات بالا، منظور از \(\mathbb{N}\) مجموعه‌ی اعداد طبیعی و منظور از \(\mathbb{Z}\) مجموعه‌ی اعداد صحیح است.

برنامه‌ای بنویسید که \(q\) پرسمان به صورت \((l,r)\) دریافت کند و به ازای هر پرسمان تعداد نابجایی‌های دنباله‌ی \(g(l), g(l+1), \ldots, g(r)\) را محاسبه کند. با توجه به این‌که پاسخ پرسمان‌ها می‌تواند بزرگ باشد، باقی‌مانده‌ی آن بر \(10^9 + 7\) را محاسبه کنید.

تعداد نابجایی‌های دنباله‌ی \(a_1, a_2, \ldots, a_n\) برابر است با تعداد جفت \((i,j)\) هایی که \(i < j\) و \(a_i > a_j\) است.

ورودی

در سطر اول ورودی عدد طبیعی \(q\)، تعداد پرسمان‌ها، آمده است.

در هر یک از \(q\) سطر بعدی به ترتیب دو عدد طبیعی \(l\) و \(r\) آمده است.

\[1\leq q\leq 50\ 000\] \[1\leq l \leq r\leq 10^{18}\]

خروجی

خروجی شامل \(q\) سطر است که در \(i\) امین \((1\leq i\leq q)\) سطر از آن، پاسخ پرسمان \(i\) ام آمده است.

زیرمسئله‌ها

زیرمسئله	نمره	محدودیت
۱	۲۵	\(l,r \leq 1\ 000\ 000\)
۲	۲۵	\(r - l \leq 100, q \leq 10\ 000\)
۳	۵۰	بدون محدودیت اضافی

مثال

ورودی نمونه ۱

4
1 1
2 3
1 5
3 17

خروجی نمونه ۱

0
0
2
25