Flea's High Wire Jump

In city \(Z\) there live many fleas. In the Z City Saturday Life Channel there is an entertainment show. In the show one flea is invited to a high wire positioned at the center of an infinitely long wire. The show host gives the flea a card containing \(N+1\) nonnegative integers written on it. The last number is \(M\), and each of the first \(N\) numbers is at most \(M\) (repetitions are allowed). In every jump, the flea may choose any number \(S\) from the card, and then jump either \(S\) units to the left or \(S\) units to the right. The flea's final task is to land exactly 1 unit to the left of its starting position in order to pick up a gift.

For example, when \(N=2, M=18\):

• The flea holding the card (10, 15, 18) can finish the task. One possible sequence is: first jump 10 units to the left; then make three consecutive left jumps of 15 units each; finally, make three consecutive right jumps of 18 units each.
• The flea holding the card (12, 15, 18) cannot ever achieve the target.

For fixed \(N\) and \(M\), there are \(M^N\) different cards (the first \(N\) numbers vary while the last is always \(M\)). The problem asks: among all these cards, how many allow the flea to complete its task?

Observation: The flea can make an arbitrary number of jumps with any of the numbers in the card. It turns out that the flea can reach the target if and only if the greatest common divisor (gcd) of the set of available jump lengths (i.e. the first \(N\) numbers and \(M\)) is 1. In other words, a card is valid if and only if \[ gcd(a_1, a_2, \dots, a_N, M) = 1. \] Using the principle of inclusion–exclusion (Möbius inversion), the number of valid cards is given by: \[ \text{Answer} = \sum_{d\mid M} \mu(d) \left(\frac{M}{d}\right)^N, \] where \(d\) runs over all divisors of \(M\) and \(\mu\) is the Möbius function.

inputFormat

The input consists of a single line containing two integers \(N\) and \(M\) where \(N\) is the number of free numbers on the card (other than the fixed \(M\)) and \(M\) is the fixed largest number on the card. You may assume that \(1 \leq N \leq 10^5\) and \(1 \leq M \leq 10^5\) (or as specified by the problem constraints).

outputFormat

Output a single integer: the number of cards (out of \(M^N\) total) that allow the flea to eventually jump to exactly 1 unit to the left of the starting point.

sample

2 18

216