+ محدودیت زمان: ۲ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت + منبع: آزمون مقدماتی اول دوره ۲۶ المپیاد کامپیوتر ---------- توابع $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 ```