30413번 - 양 한 마리... 양 A마리... 양 A제곱마리...

문제

(削除) (잠이 안 오는 춘배의 모습) (削除ここまで)

춘배는 오늘도 열심히 활동을 마친 후 자려 하지만 도저히 잠이 안 온다. 춘배는 잠을 자기 위해 자신만의 방법으로 양을 세려는데 한 마리씩 세지 않고 여러 마리를 한꺼번에 세면서 자려 한다.

춘배는 일단 양의 정수 $A$를 정한다. 그 후 양을 셀 때 첫 번째에 센 양의 수는 항상 1ドル$로 두고, 그 뒤 두 번째에 센 양의 수는 $A,ドル 세 번째에 센 양의 수는 $A^{2}$ 이렇게 점점 양의 수를 세어 간다. 즉, $n$번째에 센 양의 수는 $A^{n-1}$ 가 된다.

춘배는 이러한 방식으로 양을 세다 문득 자신이 첫 번째부터 $B$번째까지 센 모든 양의 수가 얼마나 될지 궁금해졌다. 춘배를 위해 첫 번째부터 마지막 $B$번째까지 센 모든 양의 수가 몇 마리인지 구해보자! 하지만 수가 너무 커질 수 있기에 1ドル,000円,000円,007円(= 10^{9} + 7)$로 나눈 나머지를 구하자.

입력

첫 번째 줄에 양의 정수 $A,ドル $B$ 가 공백으로 구분되어 주어진다. $(1 \le A \le 1,000円,ドル $ 1 \le B \le 10^{12})$

출력

첫 번째부터 $B$번째까지 센 모든 양의 수를 1ドル,000円,000円,007円$로 나눈 나머지를 출력한다.

제한

힌트

춘배는 똑똑해서 1ドル,000円,000円,007円$이 소수란 걸 알고있다.