Problem8245--ABC278 —— Ex - make 1

8245: ABC278 —— Ex - make 1

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 256 MiB

SubmitSolved: 1Submit Num: 1StatisticsShowOff!

Description

A sequence S of non-negative integers is said to be a good sequence if:
  • there exists a non-empty (not necessarily contiguous) subsequence T of S such that the bitwise XOR of all elements in T is 1.
There are an empty sequence A, and $2^B$ cards with each of the integers between 0 and $2^B−1$ written on them.
You repeat the following operation until A becomes a good sequence:
  • You freely choose a card and append the integer written on it to the tail of A. Then, you eat the card. (Once eaten, the card cannot be chosen anymore.)
How many sequences of length N can be the final A after the operations? Find the count modulo 998244353.

Input

The input is given from Standard Input in the following format:
$N\ B$

Output

Print the answer.

Constraints

$1≤N≤2×10^5$
$1≤B≤10^7$
$N≤2^B$
N and B are integers.

Sample 1 Input 

2 2

Sample 1 Output 

5

The following five sequences of length 2 can be the final A after the operations.

  • (0,1)
  • (2,1)
  • (2,3)
  • (3,1)
  • (3,2)

Sample 2 Input 

2022 1119

Sample 2 Output 

293184537

Sample 3 Input 

200000 10000000

Sample 3 Output 

383948354

Source/Category

 
Submit