409978: GYM103886 E Jeopardized Projects

Eric has joined his district science fair with his engineering project The Palindromic Cereal Bridge. Envy is envious of Eric's unique project, so he decides to ruin it while Eric goes to talk with the CerealCodes team.

A project can be described by an array $$$a_1, a_2, \ldots, a_k$$$ of length $$$k$$$ consisting of positive integers. We call a project jeopardized if it is not palindromic  — that is, there is some $$$1 \le i \le k$$$ such that $$$a_i \neq a_{k - i + 1}$$$.

Envy likes the integers $$$l$$$ and $$$r$$$, and wants to know how many jeopardized projects there are satisfying the following: $$$$$$l \le \sum\limits_{i = 1}^{k}a_i \le r$$$$$$

Since the answer may be very large, output it modulo $$$1\,000\,000\,007$$$.

Please help him figure this out!

The input consists of multiple tests. The first line contains $$$t$$$, the number of test cases ($$$1 \le t \le 2 \cdot 10^5$$$).

The only line of each test case contains $$$l$$$ and $$$r$$$ ($$$1 \le l \le r \le 10^5$$$).

For each test case, print the answer, modulo $$$1\,000\,000\,007$$$.

4
2 3
1 1
4 4
123 456

2
0
4
318860857

In the first test, there are $$$2$$$ jeopardized arrays:

• $$$[1, 2]$$$
• $$$[2, 1]$$$

In the second test, there are no jeopardized arrays.

In the third test, there are $$$4$$$ jeopardized arrays:

• $$$[1, 1, 2]$$$
• $$$[2, 1, 1]$$$
• $$$[3, 1]$$$
• $$$[1, 3]$$$

Problem Credits: Jesse Choe and Eric Hsu