Bored out of your mind on a long car ride, you decide to try out a peculiar single-player game. Upon opening the box, you discover a cardboard circle, divided into $N$ slices, as well as a single token. The topmost section is inscribed with the integer $N$, and the $i^{\text{th}}$ segment in the clockwise direction is marked with the integer $N-i$. The token is then placed on the piece labelled $N$. You are given $K$ turns, where during each turn, you may move the token either one or two tiles forward in the clockwise direction, returning to the piece marked with $N$ after each loop.

After all the turns have elapsed, your total score is calculated by calculating the sum of values that the token ended on after each turn, meaning that the score of the tile that the token starts on during the first turn is not counted. Can you determine the maximum possible score that you can obtain after playing optimally for $K$ turns, taken modulo ${10}^9+7$?

Constraints

For all subtasks, $1\le N\le 100$.

Subtask 1 [30%]

$1\le K\le {10}^5$

Subtask 2 [70%]

$1\le K\le {10}^{18}$

Input Specification

The first and only line of input will contain the integers $N$ and $K$, in that order.

Output Specification

Output, on a single line, the maximum score that can be achieved within $K$ moves.

Sample Input

5 5

Sample Output

18

Explanation of Sample Output

The best score you can obtain is by moving to the tiles $5\to 4\to 2\to 5\to 4\to 3$, obtaining a final score of $4+2+5+4+3=18$.