B. Boundless Deck
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Henrique Ramos is very happy with his new purchase: a special deck with infinitely many cards!

Each card in this deck has a number written on it. When buying the deck, Henrique had to choose a positive integer $$$n$$$, which determines the numbers on the cards.

The number on the first card is $$$n^0$$$, the second card has $$$n^1$$$, the third has $$$n^2$$$, and in general, the $$$i$$$-th card has the number $$$n^i$$$. This way, each card is unique, and no two cards have the same number.

Henrique is going to play a game with his friends using his new deck. In this game, a move is defined as a finite subset of cards from the deck, and the value of each move is the sum of the numbers on the selected cards.

For example, Henrique's deck for $$$n = 3$$$ contains the cards $$$1, 3, 9, 27, 81$$$, and so on. In this same example, a few valid moves are:

  • $$$1$$$, with value $$$1$$$;
  • $$$1, 3$$$, with value $$$4$$$;
  • $$$3, 243, 729$$$, with value $$$975$$$.

Henrique is interested in the moves with the smallest values, so he created a sequence of all possible move values, ordered by their value. For example, the first five terms of this sequence for $$$n = 3$$$ are: $$$1, 3, 4, 9, 10$$$.

Henrique wants to know the $$$k$$$-th term of this sequence. However, he's currently too busy reading the problem Collatz-Star of Pain and Suffering. Help Henrique by calculating the value of the $$$k$$$-th term in this sequence.

Since the answer can be a very large number, print only the remainder when it is divided by $$$10^9 + 7$$$.

Input

The input is a single line containing two integers $$$n$$$ and $$$k$$$ ($$$2 \leq n \leq 10^9, 1 \leq k \leq 10^9$$$). $$$n$$$ is the number that defines Henrique's deck, and $$$k$$$ is the index Henrique is interested in.

Output

Output a single integer: the remainder when the $$$k$$$-th term of this sequence is divided by $$$10^9 + 7$$$.

Examples
Input
3 4
Output
9
Input
4 5
Output
17
Input
3 98
Output
975
Note

In the first test case, the first five terms of this sequence are: $$$1, 3, 4, 9, 10$$$. The fourth term is $$$9$$$.

In the second test case, the first five terms of this sequence are: $$$1, 4, 5, 16, 17$$$. The fifth term is $$$17$$$.