J. Dyscalculia
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

KaitoKid is, obviously, a kid. He's interested in mathematics despite his young age. Today, he was trying to count.

KaitoKid starts counting from one. At the first second, he always says one. At each of the next seconds, he either says the next number of the one he said the second before, or gets lost and starts counting from one again.

More formally, KaitoKid will count for $$$n$$$ seconds. At each second $$$i$$$ he says the number $$$a_i$$$ where:

  • If $$$i=1$$$, $$$a_i=1$$$.
  • Otherwise, $$$a_i = 1$$$ or $$$a_i = a_{i-1} + 1$$$

As a grandmaster at a young age, that looked so easy to do, so he decided to find the sum of the sum of the $$$k$$$ lexicographically smallest arrays he could possibly say, modulo $$$10^9+7$$$

Input

The first line of the input contains two space-separated integer numbers $$$n$$$ and $$$k$$$ $$$(1 \le n \le 10^5), (1 \le k \le 10^9)$$$

It is guaranteed that $$$k$$$ is always less than or equal to the number of possible arrays

Output

Output a single integer number. The sum of the sum of the $$$k$$$ lexicographically smallest arrays he could possibly say modulo $$$10^9+7$$$

Example
Input
3 3
Output
11
Note

As $$$n = 3$$$, the possible arrays he can say in lexicographical order are:

  • 1 1 1
  • 1 1 2
  • 1 2 1
  • 1 2 3

Their sums are $$$3, 4, 4, 6$$$, respectively. The sum of the lexicographically smallest $$$3$$$ is $$$3+4+4 = 11$$$, Hence, the answer is $$$11$$$