Perfect Square Factorial Transformation

Let \(S_n = \{1,2,\dots,n\}\) be the set of positive integers up to \(n\). You are allowed to delete some elements from \(S_n\). Deleting an element with value \(i\) costs \(i^k\) and each element can be deleted at most once.

After some deletions, let the product of the remaining elements be \(P\). We want \(P\) to be a perfect square. In other words, if the prime factorization of \(P\) is \(\prod_p p^{e_p}\), then each exponent \(e_p\) must be even. Equivalently, if we denote by \(v_p(i)\) the exponent of the prime \(p\) in \(i\) and define a bit vector for each \(i\) as \(B(i) = (v_p(i) \bmod 2)_p\), then the condition is that

\(\bigoplus_{i \in S_n \setminus D} B(i) = \mathbf{0}\),

where \(D\) is the set of deleted elements and \(\oplus\) means bitwise XOR over \(\mathbb{F}_2\).

Observing that the bitwise XOR of the entire set \(S_n\) is

\(R = \bigoplus_{i=1}^n B(i)\),

we must choose a set \(D\) such that

\(\bigoplus_{i \in D} B(i) = R\).

A natural strategy is to note that for any prime \(p\) the exponent of \(p\) in \(n!\) is \[ e_p(n!) = \sum_{j\ge1} \left\lfloor \frac{n}{p^j} \right\rfloor, \] so the parity of \(e_p(n!)\) is given by \(e_p(n!)\bmod2\). In particular, if we define the squarefree part of \(n!\) as \[ R_{sf} = \prod_{p\le n \text{ with } e_p(n!)\equiv1\, (\bmod\, 2)} p, \] then deleting exactly the primes \(p\) for which \(e_p(n!)\) is odd will make the product of the remaining elements a perfect square.

Your task is, given a fixed positive integer \(k\) and \(T\) queries, each query containing an integer \(n\), compute the minimum total deletion cost (i.e. the sum of \(i^k\) for the deleted elements) required to transform \(S_n\) so that the product of the remaining numbers is a perfect square. Since the answer can be large, output it modulo \(998244353\).

Note: You need to compute the minimum deletion cost and then take it modulo \(998244353\), rather than minimizing the cost after taking the modulo.

inputFormat

The first line contains two integers \(T\) and \(k\) \((1 \le T \le 10^5,\ 1 \le k \le 10^9)\): the number of queries and the exponent used in deletion cost, respectively.

Each of the next \(T\) lines contains a single integer \(n\) \((1 \le n \le N_{\max})\), representing a query.

outputFormat

For each query, output a single integer: the minimal deletion cost modulo \(998244353\) required to make the product of the remaining numbers in \(S_n\) a perfect square.

sample

3 1
2
3
8

2
5
14

</p>