As a journalist, Bobo was asked to write a report about Boboland of length
nnn. Bobo initially wanted to write a report that was both complimentary and critical, but he was afraid that malicious people might take his words out of context and turn it into a critique of Boboland. A report of length
nnn can be seen as a sequence of integers
a1,...,an where
−m≤ai≤m represents a statement with a praise degree of
ai . If there are
k consecutive statements in the report that have a total praise degree less than
0 and satisfy
k≥2 , then these
k statements may be taken out of context by malicious people to attack Bobo. Bobo does not want this to happen and wants to know how many different reports he can write without being taken out of context.
Formally, you need to calculate the number of integer sequences
a1,a2,…,an of length
nnn that satisfy:
-
For all 1≤i≤n , it holds that −m≤ai≤m .
-
For all 1≤l<r≤n , it holds that ∑i=lrai≥0 .
Since the answer may be large, you need to output it modulo
998244353 .