Counting Valid Non‐Decreasing Sequences

Given two positive integers n and k, count the number of sequences a₁, a₂, ..., a_n of positive integers satisfying:

• \(0 < a_1 \le a_2 \le \dots \le a_n \le k\).

• For all \(i \neq j\), \(a_i + a_j \neq k+1\).

Since the answer might be large, output it modulo \(10^9+7\).

Explanation:

The first condition forces the sequence to be non‐decreasing with each \(a_i\) in the range \([1,k]\). The second condition disallows any two (not necessarily adjacent) numbers from being complementary with respect to \(k+1\). In other words, if a number \(x\) appears (with positive frequency) then its complement \(k+1-x\) cannot appear. In the special case when \(2x=k+1\) (which can only happen if \(k\) is odd), the number \(x\) can appear at most once, because otherwise two copies of \(x\) would form a forbidden pair.

This combinatorial problem can be solved by first considering the valid choices of numbers to appear (with the complementary constraint) and then distributing the \(n\) positions among the selected numbers (each selected number gets at least one occurrence, with the exception of the special number when \(k\) is odd, which, if chosen, may only appear once). Using generating functions one obtains that the answer is given by the coefficient of \(x^n\) in \[ \frac{(1+x)^{m+\epsilon}}{(1-x)^m}, \] where \(m = \lfloor k/2\rfloor\) and \(\epsilon = 1\) if \(k\) is odd, and \(\epsilon = 0\) if \(k\) is even. This coefficient can be computed via the combinatorial formula \[ \text{Answer} = \sum_{r=0}^{m+\epsilon} \binom{m+\epsilon}{r}\, \binom{m+n-r-1}{n-r}\n\] mod \(10^9+7\), with the convention that when \(k=1\) (and hence \(n\) must be 1) the answer is 1 (and 0 for larger \(n\)).

inputFormat

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

\(1 \le n, k\)

outputFormat

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

sample

1 1

1