P2231 [HNOI2002] Flea

Many fleas live in Z City. There is an entertainment show on the Saturday Life channel in Z City. A flea will be placed at the exact middle of a high wire. The wire is very long and can be regarded as infinite. The host will give the flea a card. The card has $N+1$ positive integers. The last one is $M$, and each of the first $N$ numbers does not exceed $M$. Duplicate numbers are allowed on the card. Each time, the flea can choose any positive integer $S$ from the card and then jump $S$ units either to the left or to the right. Its task is to end up at the point located one unit to its left and pick up the gift there. For example, when $N=2, M=18$, a flea holding the card $(10, 15, 18)$ can complete the task: it can first jump $10$ units to the left, then jump left $3$ more times, $15$ units each time, and finally jump right $3$ times, $18$ units each time. However, with the card $(12, 15, 18)$, it is impossible to reach the point one unit to its left. When $N$ and $M$ are fixed, there are clearly $M^N$ different cards. The question is: among all these cards, how many of them can complete the task?

The input consists of a single line with two integers $N$ and $M$ separated by a space.

Output a single line containing the number of cards that can complete the task. Constraints $1 \le N \le M \le 10^8$, and $M^N \le 10^{16}$.

These 12 cards are: $(1, 1, 4), (1, 2, 4), (1, 3, 4), (1, 4, 4), (2, 1, 4), (2, 3, 4)$ $(3, 1, 4), (3, 2, 4), (3, 3, 4), (3, 4, 4), (4, 1, 4), (4, 3, 4)$ Translated by ChatGPT 5