Home

Problem Statement

There is a regular $N$-gon with side length $D$.

Starting from a vertex, we place black or white stones on the circumference at intervals of $1$. As a result, each edge of the $N$-gon will have $(D+1)$ stones on it, for a total of $ND$ stones.

How many ways are there to place stones so that all edges have the same number of white stones on them? Find the count modulo $998244353$.

Constraints

• $3 \leq N \leq 10^{12}$
• $1 \leq D \leq 10^4$
• All values in input are integers.

Sample Input 1

3 2

Sample Output 1

10

There are $10$ ways, as follows:

Sample Input 2

299792458 3141

Sample Output 2

138897974

Find the count modulo $998244353$.