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

\begin{equation*} f(n)= \begin{cases} 1, & n \equiv 1 \pmod 3 \\ -1, & n \equiv 2 \pmod 3 \\ f(\frac{n}{3}), & n \equiv 0 \pmod 3 \\ \end{cases} \end{equation*}

\begin{equation*} g(n)=\sum_{i=1}^{n}f(i) \end{equation*}

در توضیحات بالا، منظور از $\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$ آمده است.

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

• زیرمسئله اول (۲۵ نمره): $l,r \leq 10^6$
• زیرمسئله دوم (۲۵ نمره): $r - l \leq 100, q \leq 10^4$
• زیرمسئله سوم (۵۰ نمره): بدون محدودیت اضافی

• محدودیت زمان: ۲ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت
• $1\leq q\leq 5\times 10^4$
• $1\leq l \leq r\leq 10^{18}$

• سوال بعد
• سوال قبل