Problem Statement
Given is a positive integer M and a sequence of N integers: A=(A1,A2,ldots,AN). Find the number, modulo 998244353, of sequences of N+1 integers, X=(X1,X2,ldots,XN+1), satisfying all of the following conditions:
- 1leqXileqM (1leqileqN+1)
- AiXileqXi+1 (1leqileqN)
Constraints
- 1leqNleq1000
- 1leqMleq1018
- 1leqAileq109
- prodi=1NAileqM
Input is given from Standard Input in the following format:
N M
A1 A2 ldots AN
Output
Print the number of integer sequences satisfying the conditions, modulo 998244353.
Sample Output 1
Seven sequences below satisfy the conditions.
- (1,2,6), (1,2,7), (1,2,8), (1,2,9), (1,2,10), (1,3,9), (1,3,10)
Sample Output 2
Nine sequences below satisfy the conditions.
- (1,3,6), (1,3,7), (1,3,8), (1,3,9), (1,3,10), (1,4,8), (1,4,9), (1,4,10), (1,5,10)
Sample Output 3
Sample Output 4