Hôm nay, thầy giáo trên lớp của moi_hoc_code đã đưa ra một bài toán với độ khó xấp xỉ 3000 (cụ thể là 800 ) codeforces, với phần thưởng cho người đầu tiên giải được là một cặp vé xem phim. Bài toán có nội dung như sau:

Định nghĩa $f(i) = \frac{i}{p^{V_p(i)}}$. Tính $f(1) + f(2) + ... + f(n)$. Vì kết quả có thể rất lớn nên chỉ cần in ra kết quả đó sau khi chia lấy dư cho $10^9+7$.

Do moi_hoc_code mới học code nên không thể giải được bài toán siêu khủng này. Em liền đưa bài toán này cho khanhphucscratch, người mà em luôn đối xử trên cả tình bạn, với hy vọng có thể cùng nhau giành được một cặp vé xem phim chung. Tuy nhiên, khanhphucscratch, người đã có hai giải Nhất THTQG, lại chỉ giải được bài toán này với $p = 2$. Thất vọng, moi_hoc_code đành tìm đến sự trợ giúp của huyhau6a2, người cũng đã có một giải Nhất THTQG, nhưng thật không may, huyhau6a2 lại không nghiên cứu sâu về toán nên không biết $V_p(i)$ là gì. Bạn có thể giúp moi_hoc_code giải được bài toán này để giành lấy cặp vé xem phim hay không?

(Biết rằng: $V_p(i)$, hay lũy thừa của $p$ trong $i$, được định nghĩa trong bài tập này là số nguyên không âm $y$ lớn nhất không vượt quá $10^{18}$ sao cho $i \vdots p^y$. Ví dụ: Ta có $V_2(4) = 2$ do $4\vdots 2^2$ nhưng không chia hết cho $2^3$. Do đó $f(4) = \frac{4}{2^2} = 1$).

Giới hạn: $n, p \le 10^{18}$.

5 2

11