C. Counting Relative Lists
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a task to count how many lists of $$$N$$$ positive integer numbers, each less than or equal to $$$M$$$, can be formed such that adjacent numbers in the list are relatively prime. Two numbers are relatively prime if their greatest common divisor (GCD) is 1. This problem combines number theory with combinatorial counting, challenging you to explore the intricacies of prime relationships between numbers within a constrained set.

Input

Input consists of a single line containing two integers $$$N$$$ and $$$M$$$ ($$$1 \leq N \leq 10^8$$$) ($$$1 \leq M \leq 100$$$), representing the length of the lists and the maximum possible value of each element in the lists, respectively.

Output

Output a single integer, the total number of lists that can be formed under the given conditions, because the number can be very large print it modulo $$$10^9 + 7$$$.

Examples
Input
2 3
Output
7
Input
2 10
Output
63