2018 Всероссийская олимпиада школьников по информатике, Москва
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
ai describes the athlete's workload at the i-th day. Any two consecutive days should have a different load:
ai+1. To alternate the growth and decrement of the load, for i from 1 to m - 2 the following condition must satisfy: if
The total load in the implementation of the plan should be n, that is
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 (1 ≤ n ≤ 5000, 1 ≤ k ≤ n).
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 .