# [Solution] Chef And Array Construction solution codechef

Chef And Array Construction solution codechef – Given two positive integers N and M, let S denote the set of all the arrays of size N such that each element of the array lies in the range [1, M]. Since there are M^N such arrays, the size of S is M^N.

Table of Contents

## [Solution] Chef And Array Construction solution codechef

Let X_i denote the bitwise AND of all elements of the i^{th} array in the set, where 1 \le i \le M^N.
Find the value \sum_{i = 1}^{M^N} X_i. Since the answer can be huge, output the answer modulo 998244353.

### Input Format

• The first line of input will contain a single integer T, denoting the number of test cases.
• The first and only line of each test case contains two integers N and M, the size of the array, and the maximum limit of elements.

### Output Format

For each test case, print the value \sum_{i = 1}^{M^N} X_i. Since the answer can be huge, output the answer modulo 998244353.

## [Solution] Chef And Array Construction solution codechef

• 1 \leq T \leq 1000
• 1 \leq N \leq 2\cdot10^5
• 1 \leq M \leq 10^9

### Sample 1:

Input

Output

2
2 2
2 3

3
12

## [Solution] Chef And Array Construction solution codechef Explanation:

Test case 1: The set S contains \{[1,1], [1,2], [2,1], [2,2]\}. The array X = [1\& 1, 1\& 2, 2\& 1, 2\& 2] = [1, 0, 0, 2]. Thus, sum of all elements of X is 1+0+0+2 = 3.

Test case 2: The set S contains \{[1,1], [1,2], [1,3], [2,1], [2,2], [2,3], [3,1], [3,2], [3,3]\}. The array X = [1\& 1, 1\& 2, 1\& 3, 2\& 1, 2\& 2, 2\& 3, 3\& 1, 3\& 2, 3\& 3] = [1, 0, 1, 0, 2, 2, 1, 2, 3]. Thus, sum of all elements of X is 12.