oj mrJudge
Toggle navigation
  • Login
    • Forget Password
      Login
User Image

Hello, Stranger

Guest
  • Analysis Mode
  • Problems
    • All Problems
    • Latest Problems
  • Join Us Now
  • Registration
  • Contact Us
  • Infomation
  • About
    • Terms of Use
    • Technical Specifications
    • Credits

flowers Batch , stdin/stdout

Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

flowers.html

Problem Description

Ranald is eating flowers for lunch today. He has bought an infinite supply of red and white flowers.

Ranald eats flowers one by one, but he has decided that he must only eat white flowers in consecutive groups of K. There are no limitations on how and when he eats the red flowers.

There are D days he will be planning his lunches for. On each day i, he wants to eat between Ai and Bi flowers. Help him find out what is the number of possible lunches he can have for each day. Two ways are considered different if at some point in time, he eats one type of flower in one way and another type of flower in another. Since this number can be very large, output it modulo 109 + 7.

Limits

For all subtasks: 1 ≤ D ≤ 105.

Subtask 1 (17%): 1 ≤ K ≤ 18, 1 ≤ Ai ≤ Bi ≤ 18.

Subtask 2 (23%): K = 1, 1 ≤ Ai ≤ Bi ≤ 106.

Subtask 3 (24%): 1 ≤ K ≤ 106, 1 ≤ Ai = Bi ≤ 106.

Subtask 4 (36%): 1 ≤ K ≤ 106, 1 ≤ Ai ≤ Bi ≤ 106.

Subtask 5 (0%): Sample Testcases.

Input

The first line of input contains two integers, K and D.

The next D lines of input contains two integers each, Ai and Bi for each day.

Output

The output should contain D lines, with line i containing the number of possible lunches Ranald could have on day i, modulo 109 + 7.

Sample Testcase 1

Input

2 3
1 3
2 3
4 4

Output

6
5
5

Explanation

For K = 2, Rar can eat "R", "RR", "WW", "RRR", "RWW", "WWR", "WWWW" or "RWWR".

Tags

Dynamic Programming

Subtasks and Limits

Subtask Score #TC Time Memory Scoring
117211s256MBMinimum
223201s256MBMinimum
324201s256MBMinimum
436811s256MBMinimum
5011s256MBMinimum

Judge Compile Command

g++-8 ans.cpp -o flowers -Wall -Wshadow -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512

Accepted Submissions

subIDUserTimeMax Time

Past Submissions

subIDUserTimeScore
mrJudge 09.05.20
Copyright © 2020 mrJudge. All rights reserved.