Kstar is playing the latest autobattler game, Team Underground Chess. Each unit in this game is uniquely determined by two traits: size and tier. Players have the option of trading in units in to obtain better units. Specifically, for any positive ~n~, if Kstar has ~n~ units and the ~i~-th ~(1 \leq i \leq n)~ unit has size ~i~ and tier ~k~, then she can trade them all in to get a single unit of size ~n~ and tier ~k + 1~.

For example, if she has ~4~ units that are exactly:

• Size ~1~ and tier ~7~
• Size ~2~ and tier ~7~
• Size ~3~ and tier ~7~
• Size ~4~ and tier ~7~

Then she can trade them all in to get a single unit with size ~4~ and tier ~8~.

It costs ~n~ gold to purchase a unit of size ~n~ and tier ~1~. Higher tier units cannot be purchased directly. Kstar starts with no units. How much gold will it cost for her to get a unit of size ~N~ and tier ~K~? Since this number can be huge, output it modulo the prime number ~10^9 + 7~.

Constraints

~1 \leq N, K \leq 10^6~

For 20% of the points, ~1 \leq N, K \leq 3000~

Input Specification

A single line with two integers: ~N~ and ~K~.

Output Specification

A single integer, the answer, modulo ~10^9 + 7~.

Sample Input 1

3 3

Sample Output 1

10

Explanation for Sample 1

To get a unit of size ~3~ and tier ~3~, Kstar needs to trade in:

• A unit with size ~1~ and tier ~2~, which can only be obtained by trading in:
  • A unit with size ~1~ and tier ~1~, which can be bought for ~1~ gold
• A unit with size ~2~ and tier ~2~, which can only be obtained by trading in:
  • A unit with size ~1~ and tier ~1~, which can be bought for ~1~ gold
  • A unit with size ~2~ and tier ~1~, which can be bought for ~2~ gold
• A unit with size ~3~ and tier ~2~, which can only be obtained by trading in:
  • A unit with size ~1~ and tier ~1~, which can be bought for ~1~ gold
  • A unit with size ~2~ and tier ~1~, which can be bought for ~2~ gold
  • A unit with size ~3~ and tier ~1~, which can be bought for ~3~ gold

The total amount of gold she has to spend is ~(1) + (1 + 2) + (1 + 2 + 3) = 10~.

Sample Input 2

123456 654321

Sample Output 2

372912936

Explanation for Sample 2

Be careful to output the answer modulo ~10^9+7~ and beware of overflow.

Python users are encouraged to select PyPy instead of Python when submitting.