Unique Necklace Combinations

Recently, Mingming became fascinated with a type of necklace. Unlike ordinary pearl necklaces, these necklaces have beads carved out of Taishan stone in the shape of a right triangular prism. Each bead is a triangular prism whose lateral faces are squares engraved with a number. A necklace is considered satisfactory if it meets the following conditions:

1. The necklace consists of $n$ beads.
2. On every bead, each engraved number $x$ satisfies $0 < x \le a$, and the three numbers on the bead have a greatest common divisor exactly equal to $1$, i.e. \(\gcd(x,y,z)=1\).
3. Any two adjacent beads must be different. Two beads are considered identical if and only if one can be obtained from the other by rotation or reflection.
4. Two necklaces are considered the same if one can be rotated (cyclically shifted) to become the other.

Given positive integers $n$ and $a$, determine the number of different necklaces that can be formed. Since the answer may be very large, output it modulo $10^9+7$.

Explanation: First, each bead is determined by a triple $(x,y,z)$ where $1\le x,y,z\le a$ and \(\gcd(x,y,z)=1\). However, beads are considered identical if one is a rotation or reflection of the other. Let $M$ be the number of distinct bead types. Then, using these $M$ bead types, we form a necklace of $n$ beads such that adjacent beads are different (note that if $n>1$, a constant necklace is invalid). Moreover, two necklaces are considered identical if one can be rotated to obtain the other.

The solution is divided in two parts:

• Compute the number of distinct bead types $M$. Using Burnside's lemma on the dihedral group $D_3$, we have \[ M = \frac{1}{6}\Big( f_{id} + f_{r} + f_{r^2} + 3R \Big), \] where \[ f_{id} = \sum_{d=1}^{a} \mu(d) \Big(\lfloor \frac{a}{d}\rfloor\Big)^3, \quad R = \sum_{d=1}^{a} \mu(d) \Big(\lfloor \frac{a}{d}\rfloor\Big)^2, \] and \(\mu(\cdot)\) is the Möbius function. Note that $f_{r}=f_{r^2}=1$ when $a\ge1$ because a bead fixed under a nontrivial rotation must have all three numbers equal, and the gcd condition forces that number to be $1$.
• Count the number of necklaces. For $n=1$, the answer is simply $M$. For $n>1$, we count necklaces (cyclic arrangements) using the $M$ bead types with the restriction that adjacent beads must be different. Viewing this as a cyclic coloring of $n$ positions with $M$ colors (with no two adjacent colors equal), the total number of valid colorings (if positions were labeled) is \[ P = (M-1)^n + (-1)^n (M-1). \] However, since two necklaces are considered the same if they can be rotated to obtain each other, we apply Burnside's lemma over the cyclic rotations. In detail, for each rotation by $r$ positions (with \(0\le r1$, the answer is given by \[ \text{Answer} = \frac{1}{n}\sum_{d\mid n} \varphi\Big(\frac{n}{d}\Big) \Bigl[ (M-1)^d + (-1)^d (M-1) \Bigr] \pmod{10^9+7}. \]

Your task is to implement this computation in five different programming languages.

inputFormat

The input consists of a single line with two integers $n$ and $a$, where $n$ is the number of beads in the necklace and $a$ is the maximum number on a bead ($1 \le n, a \le$ constraints as in the problem).

outputFormat

Output a single integer, the number of different necklaces modulo $10^9+7$.

sample

1 1

1