توابع f:N→{−1,1} و g:N→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 ام آمده است.