Tổng GCD Của Mọi Dãy

Xét mọi dãy có thứ tự độ dài $N$, mỗi phần tử thuộc đoạn từ $1$ đến $K$. Tính tổng gcd của các phần tử trên toàn bộ các dãy đó.

Có đúng $K^N$ dãy như vậy. Với mỗi dãy, lấy ước chung lớn nhất của toàn bộ $N$ phần tử rồi cộng các giá trị này.

Input

• Một dòng chứa hai số nguyên $N$ và $K$.

Output

• In tổng cần tìm theo modulo $1000000007$.

Constraints

• $2\le N\le 10^5.$
• $1\le K\le 10^5.$
• $N$ và $K$ là số nguyên.

Scoring

• Subtask $1$ ($50\%$ số điểm): $N\le 8$ và $K\le 8$.
• Subtask $2$ ($50\%$ số điểm): Không có giới hạn bổ sung.

Example

2 3

12