409978: GYM103886 E Jeopardized Projects

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

E. Jeopardized Projectstime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

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!

Input

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$$$).

Output

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

ExampleInput
4
2 3
1 1
4 4
123 456
Output
2
0
4
318860857
Note

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

加入题单

上一题 下一题 算法标签: