{"raw_statement":[{"iden":"problem statement","content":"You are given positive integers $N$ and $M$. For each $k=1,\\ldots,N$, solve the following problem.\n\n*   Problem: We will divide $N$ people with ID numbers $1$ through $N$ into $k$ non-empty groups. Here, people whose ID numbers are equal modulo $M$ cannot belong to the same group.  \n    How many such ways are there to divide people into groups?  \n    Since the answer may be enormous, find it modulo $998244353$.\n\nHere, two ways to divide people into groups are considered different when there is a pair $(x, y)$ such that Person $x$ and Person $y$ belong to the same group in one way but not in the other."},{"iden":"constraints","content":"*   $2 \\leq N \\leq 5000$\n*   $2 \\leq M \\leq N$\n*   All values in input are integers."},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$N$ $M$"},{"iden":"sample input 1","content":"4 2"},{"iden":"sample output 1","content":"0\n2\n4\n1\n\nPeople whose ID numbers are equal modulo $2$ cannot belong to the same group. That is, Person $1$ and Person $3$ cannot belong to the same group, and neither can Person $2$ and Person $4$.\n\n*   There is no way to divide the four into one group.\n*   There are two ways to divide the four into two groups: ${{1,2},{3,4}}$ and ${{1,4},{2,3}}$.\n*   There are four ways to divide the four into three groups: ${{1,2},{3},{4}}$, ${{1,4},{2},{3}}$, ${{1},{2,3},{4}}$, and ${{1},{2},{3,4}}$.\n*   There is one way to divide the four into four groups: ${{1},{2},{3},{4}}$."},{"iden":"sample input 2","content":"6 6"},{"iden":"sample output 2","content":"1\n31\n90\n65\n15\n1\n\nYou can divide them as you like."},{"iden":"sample input 3","content":"20 5"},{"iden":"sample output 3","content":"0\n0\n0\n331776\n207028224\n204931064\n814022582\n544352515\n755619435\n401403040\n323173195\n538468102\n309259764\n722947327\n162115584\n10228144\n423360\n10960\n160\n1\n\nBe sure to find the answer modulo $998244353$."}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}