+ محدودیت زمان: ۲ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- توابع $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 5\times 10^4$$ $$1\leq l \leq r\leq 10^{18}$$ # خروجی خروجی شامل $q$ سطر است که در $i$ امین $(1\leq i\leq q)$ سطر از آن، پاسخ پرسمان $i$ ام آمده است. # زیرمسئله‌ها **الف)** $l,r \leq 10^6$ (۲۵ نمره) **ب)** $r - l \leq 100, q \leq 10^4$ (۲۵ نمره) **ج)** بدون محدودیت اضافی (۵۰ نمره) # مثال ## ورودی نمونه ``` 4 1 1 2 3 1 5 3 17 ``` ## خروجی نمونه ``` 0 0 2 25 ```