Cho 2 số nguyên dương ~n~ và ~k~. Một số ~mim~ cơ số ~x~ được định nghĩa là một số có thể thu được từ tổng các lũy thừa riêng biệt của ~x~.

Ví dụ, với ~n=3~, các số ~mim~ có thể là ~9 = 3^2~, ~12=3^2+3^1~, ~37=3^3+3^2+3^0…~ Trong khi đó, với ~n=3~, các số 2, 5, 18, … không phải là một số ~mim~.

Vậy, với số ~n~ và ~k~ cho trước, hãy tìm số ~mim~ thứ ~k~ theo thứ tự tăng dần. Vì kết quả có thể rất lớn nên hãy in ra theo module ~10^9+7~.

Input

2 số tự nhiên ~n~ và ~k~.

Output

Số ~mim~ cơ số ~n~ thứ ~k~.

Sample Test

Input:

3 2

Output:

3

Ràng buộc:

• Subtask 1: ~n = 2, k \le 10^{18}~ (30%)
• Subtask 2: ~2 \le n \le 100, k \le 10^{18}~ (70%)