====== هنگ ۳(mod۳) ======



توابع 
$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}$

===== ورودی و خروجی نمونه =====

<WRAP :en>
^  ورودی نمونه  ^  خروجی نمونه  ^
|4 \\ 1 1 \\ 2 3 \\ 1 5 \\ 3 17|0 \\ 0 \\ 2 \\ 25|
</WRAP>







  * [[سوال ۳|سوال بعد]]
  * [[سوال ۱|سوال قبل]]