Maximum Sum Path in a Number Triangle

Consider a triangle of numbers with (N) rows defined as follows:

• The 1st row contains (1).
• The 2nd row contains the numbers (2) to (3).
• The 3rd row contains (4) to (6).
• The 4th row contains (7) to (10).
• (\cdots)
• The (N)th row contains (N) numbers: (\frac{N(N-1)}{2}+1) to (\frac{N(N+1)}{2}).

Let the element in the (i)th row and (j)th column be denoted by ((i,j)). Two numbers ((i,j)) and ((k,\ell)) are considered directly connected if either one of them can directly reach the other. In particular, it is given that ((i,j)) can directly reach ((i+1,j)) and ((i+1,j+1)), and vice‐versa, i.e. ((i+1,j)) or ((i+1,j+1)) can reach ((i,j)) directly.

You are allowed to choose any number in the triangle as the starting point. From that starting number, you must form a continuous path by moving from one number to an adjacent number (as defined above) such that exactly (K) distinct numbers are visited consecutively. Your task is to compute the maximum possible sum of the numbers along such a path. Since the answer might be large, output it modulo (10^9+7).

inputFormat

The input consists of a single line containing two integers (N) and (K), where (N) is the number of rows in the triangle and (K) is the number of numbers to be visited in a continuous path.

outputFormat

Output a single integer: the maximum sum of a continuous path of (K) distinct numbers in the triangle, taken modulo (10^9+7).

sample

5 3

33