favorite We need a little bit of your help to keep things running, click on this banner to learn more

2018 Всероссийская олимпиада школьников по информатике, Москва

Interval trainings

The Academy of Physical Culture has developed a new method of interval training for athletes. In accordance with this method, the athlete must train every day, but the increase in load must be constantly replaced by its decrease and vice versa.

The workout plan is a set of positive integers a1, a2, ..., am, where ai describes the athlete's workload at the i-th day. Any two consecutive days should have a different load: aiai+1. To alternate the growth and decrement of the load, for i from 1 to m - 2 the following condition must satisfy: if ai < ai+1, then ai+1 > ai+2, if ai > ai+1, then ai+1 < ai+2.

The total load in the implementation of the plan should be n, that is a1 + a2 + ... + am = n. There are no restrictions on the number of days in the plan, m can be any, but the load on the first day of training is fixed: a1 = k.

Before testing a new method, the academy wants to find out how many different training plans satisfy the described limitations.

Write a program that, given the specified n and k, determines how many different workout plans satisfy the described limitations, and prints the remainder of dividing the number of such plans by the number 109 + 7.


Two integers n and k (1n5000, 1kn).


Print one number: the remainder of dividing the number of workout plans by 109 + 7.


In the first example, the following plans are suitable: [2, 1, 2, 1], [2, 1, 3], [2, 3, 1], [2, 4].

In the second example the only suitable plan is [3].

Time limit 2 second
Memory limit 512 MiB
Input example #1
6 2
Output example #1
Input example #2
3 3
Output example #2
Source 2019 All Russia school informatics olympiad, Regional stage, Day 2, Moscow, January 28, Problem B