Codeforces Round 865 (Div. 1) |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

bitmasks

combinatorics

dp

math

*2600

No tag edit access

The problem statement has recently been changed. View the changes.

×
D. XOR Counting

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputGiven two positive integers $$$n$$$ and $$$m$$$. Find the sum of all possible values of $$$a_1\bigoplus a_2\bigoplus\ldots\bigoplus a_m$$$, where $$$a_1,a_2,\ldots,a_m$$$ are non-negative integers such that $$$a_1+a_2+\ldots+a_m=n$$$.

Note that all possible values $$$a_1\bigoplus a_2\bigoplus\ldots\bigoplus a_m$$$ should be counted in the sum exactly once.

As the answer may be too large, output your answer modulo $$$998244353$$$.

Here, $$$\bigoplus$$$ denotes the bitwise XOR operation.

Input

Each test consists of multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases. The description of test cases follows.

The first and only line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$0\le n\le 10^{18}, 1\le m\le 10^5$$$) — the sum and the number of integers in the set, respectively.

Output

For each test case, output the sum of all possible values of $$$a_1\bigoplus a_2\bigoplus\ldots\bigoplus a_m$$$ among all non-negative integers $$$a_1,a_2,\ldots,a_m$$$ with $$$a_1+a_2+\ldots+a_m=n$$$. As the answer may be too large, output your answer modulo $$$998244353$$$.

Example

Input

769 15 20 10420 6912 2673 341000000000000000000 10

Output

69 6 0 44310 42 1369 216734648

Note

For the first test case, we must have $$$a_1=69$$$, so it's the only possible value of $$$a_1$$$, therefore our answer is $$$69$$$.

For the second test case, $$$(a_1,a_2)$$$ can be $$$(0,5), (1,4), (2,3), (3,2), (4,1)$$$ or $$$(5,0)$$$, in which $$$a_1\bigoplus a_2$$$ are $$$5,5,1,1,5,5$$$ respectively. So $$$a_1\bigoplus a_2$$$ can be $$$1$$$ or $$$5$$$, therefore our answer is $$$1+5=6$$$.

For the third test case, $$$a_1,a_2,\ldots,a_{10}$$$ must be all $$$0$$$, so $$$a_1\bigoplus a_2\bigoplus\ldots\bigoplus a_{10}=0$$$. Therefore our answer is $$$0$$$.

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: May/30/2023 20:03:52 (j2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|