{"raw_statement":[{"iden":"problem statement","content":"There is a regular $N$\\-gon with side length $D$.\nStarting 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.\nHow 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$."},{"iden":"constraints","content":"*   $3 \\leq N \\leq 10^{12}$\n*   $1 \\leq D \\leq 10^4$\n*   All values in input are integers."},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$N$ $D$"},{"iden":"sample input 1","content":"3 2"},{"iden":"sample output 1","content":"10\n\nThere are $10$ ways, as follows:\n![image](https://img.atcoder.jp/abc256/ba2bebe9d374f281e2b44e36231abae2.png)"},{"iden":"sample input 2","content":"299792458 3141"},{"iden":"sample output 2","content":"138897974\n\nFind the count modulo $998244353$."}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}