Background

Special for beginners, ^_^

Description

小明最近在自学化学，并对天平产生了浓厚的兴趣，于是从实验室借来一台天平。小明发现，这台天平配的砝码都是某个正整数K（2<=K<=1e9）的非负整数幂次，并且砝码没有相同的质量。假设砝码只能放在天平的右边。问能准确称量的第n（1<=n<=1e18）小的物体的质量多少？

Format

Input

每行(不超过1e6行)两个正整数包含两个整数n和K。

Output

每行一个整数，表示答案（mod 1e9+7）。

Samples

5 3
1 3

10
1

Limitation

1s, 1024KiB for each test case.