Counting Valid Sequences

Given two positive integers \(n\) and \(k\), count the number of sequences \(a = [a_1, a_2, \dots, a_n]\) of length \(n\) such that:

• \(0 < a_1 \le a_2 \le \cdots \le a_n \le k\), and
• For all \(i \neq j\), \(a_i + a_j \le k+1\).

The answer is to be output modulo \(10^9+7\).

Explanation:

Since the sequence is non-decreasing, the largest element is \(a_n\). Therefore the second condition \(a_i+a_j\le k+1\) for any \(i\neq j\) is equivalent to requiring \(2a_n \le k+1\), or equivalently

[ a_n\le \left\lfloor\frac{k+1}{2}\right\rfloor. ]

Thus each (a_i) must be chosen from the set ({1,2,\dots, M}) with (M=\left\lfloor\frac{k+1}{2}\right\rfloor). The number of non-decreasing sequences of length (n) with values in ([1, M]) is given by the stars and bars formula, i.e.,

[ \binom{n+M-1}{n} \quad\text{or}\quad \binom{n+M-1}{M-1}. ]

inputFormat

The input consists of a single line containing two integers \(n\) and \(k\) separated by a space.

\(1 \le n, k \le \text{reasonable limits}\).

outputFormat

Output a single integer, the number of valid sequences modulo \(10^9+7\).

sample

1 1

1