As a foodie, Diana loves eating snacks. One day, her snacks were all confiscated by Bella, so Diana decided to buy some more in a snack shop.
There are totally n different type of snacks in the snack shop, numbered from 1,2,…,n. Each of snacks has two sizes of packages, big ones and small ones. Diana wants to taste different snacks as many as possible, so she will buy at most 1 package for each type of snacks. For any two adjacent kinds of snacks(no matter the size), Diana can choose to buy them as a bundle, so that she could have a discount compared to buying them respectively. To simplify this problem, we assume that any small package of snacks costs 1 coin, any big one costs 2 coins and any discount is 1 coin. Now Diana wonders how many different ways to buy snacks with just kcoins.
Please output the answer module 998244353 for each k∈[1,m].
Two ways are considered the same if types of snacks, sizes of snacks and bundles are all the same.
Notice: For two adjacent kinds of snacks, Diana could either buy them respectively without a discount or buy them as a bundle, and they are considered as different ways.
For example: when n=2,k=2, there are 5 different ways:
(1b),(2b),(1s&2b),(1b&2s),(1s)(2s)
(number means the type of snack, s means its a small package, b means its a big package, & means its a bundle)