Natural Number Sums

Time limit1sMemory limit1024 MB

Summary

Count sets of distinct integers from 1 to N, none a multiple of K, with an even number of elements that sum to N, modulo 998244353.

문제

Two integers $N$ and $K$ are given. Find the number of sets $S$ that satisfy all of the following conditions, modulo $998\,244\,353$ .

Every element of $S$ is a distinct positive integer at most $N$ that is not a multiple of $K$ .
$|S|$ is even.
The sum of all elements of $S$ is $N$ .

The first line contains the number of test cases $T$ .

Each test case is given on one line with two integers $N$ and $K$ .

For each test case, print the answer on its own line.