Once upon a time, Oolimry saw a suffix array. He wondered how many strings can produce this suffix array.

More formally, given a suffix array of length $n$ and having an alphabet size $k$, count the number of strings that produce such a suffix array.

Let $s$ be a string of length $n$. Then the $i$-th suffix of $s$ is the substring $s[i \ldots n-1]$. A suffix array is the array of integers that represent the starting indexes of all the suffixes of a given string, after the suffixes are sorted in the lexicographic order. For example, the suffix array of oolimry is $[3,2,4,1,0,5,6]$ as the array of sorted suffixes is $[{imry},{limry},{mry},{olimry},{oolimry},{ry},{y}]$.

A string $x$ is lexicographically smaller than string $y$, if either $x$ is a prefix of $y$ (and $x\neq y$), or there exists such $i$ that $x_i < y_i$, and for any $1\leq j < i$ , $x_j = y_j$.


-----Input-----

The first line contain 2 integers $n$ and $k$ ($1 \leq n \leq 200000,1 \leq k \leq 200000$) — the length of the suffix array and the alphabet size respectively.

The second line contains $n$ integers $s_0, s_1, s_2, \ldots, s_{n-1}$ ($0 \leq s_i \leq n-1$) where $s_i$ is the $i$-th element of the suffix array i.e. the starting position of the $i$-th lexicographically smallest suffix. It is guaranteed that for all $0 \leq i< j \leq n-1$, $s_i \neq s_j$.


-----Output-----

Print how many strings produce such a suffix array. Since the number can be very large, print the answer modulo $998244353$.


-----Examples-----

Input
3 2
0 2 1
Output
1
Input
5 1
0 1 2 3 4
Output
0
Input
6 200000
0 1 2 3 4 5
Output
822243495
Input
7 6
3 2 4 1 0 5 6
Output
36


-----Note-----

In the first test case, "abb" is the only possible solution.

In the second test case, it can be easily shown no possible strings exist as all the letters have to be equal.

In the fourth test case, one possible string is "ddbacef".

Please remember to print your answers modulo $998244353$.

Difficulty: VERY_HARD
Tags: Combinatorics

Mathematics

Constructive algorithms

Starter code:

Solutions:
MOD = 998244353
(n, k) = map(int, input().split())
arr = list(map(int, input().split()))
pos = [0] * (n + 1)
for i in range(n):
	pos[arr[i]] = i
pos[n] = -1
cnt = 0
for i in range(n - 1):
	if pos[arr[i] + 1] > pos[arr[i + 1] + 1]:
		cnt += 1
(num, denom) = (1, 1)
for i in range(n):
	num = num * (k - cnt + n - 1 - i) % MOD
	denom = denom * (i + 1) % MOD
print(num * pow(denom, MOD - 2, MOD) % MOD)


m = 998244353
(n, k) = [int(d) for d in input().split()]
a = [int(d) for d in input().split()]
d = {}
for i in range(n):
	d[a[i]] = i
e = 0
d[n] = -1
for i in range(n - 1):
	if d[a[i] + 1] < d[a[i + 1] + 1]:
		e = e + 1
if k + e < n:
	print(0)
else:
	num = 1
	den = 1
	for i in range(1, n + 1):
		num = num * (k + e - n + i) % m
		den = den * i % m
	x = pow(den, m - 2, m)
	print(num * x % m)


MOD = 998244353
(n, k) = input().split()
n = int(n)
k = int(k)
suffix_array = input().split()
for i in range(n):
	suffix_array[i] = int(suffix_array[i])
position = [0] * (n + 1)
for i in range(n):
	position[suffix_array[i]] = i
position[n] = -1
count = 0
for i in range(n - 1):
	if position[suffix_array[i] + 1] > position[suffix_array[i + 1] + 1]:
		count += 1
(num, denom) = (1, 1)
for i in range(n):
	num = num * (k - count + n - 1 - i) % MOD
	denom = denom * (i + 1) % MOD
print(num * pow(denom, MOD - 2, MOD) % MOD)


MOD = 998244353
(n, k) = input().split()
n = int(n)
k = int(k)
suffix_array = input().split()
for i in range(n):
	suffix_array[i] = int(suffix_array[i])
position = [0] * (n + 1)
for i in range(n):
	position[suffix_array[i]] = i
position[n] = -1
count = 0
for i in range(n - 1):
	if position[suffix_array[i] + 1] > position[suffix_array[i + 1] + 1]:
		count += 1
(numerador, denominador) = (1, 1)
for i in range(n):
	numerador = numerador * (k - count + n - 1 - i) % MOD
	denominador = denominador * (i + 1) % MOD
print(numerador * pow(denominador, MOD - 2, MOD) % MOD)


import sys
from sys import stdin
mod = 998244353

def modfac(n, MOD):
	f = 1
	factorials = [1]
	for m in range(1, n + 1):
		f *= m
		f %= MOD
		factorials.append(f)
	inv = pow(f, MOD - 2, MOD)
	invs = [1] * (n + 1)
	invs[n] = inv
	for m in range(n, 1, -1):
		inv *= m
		inv %= MOD
		invs[m - 1] = inv
	return (factorials, invs)

def modnCr(n, r):
	return fac[n] * inv[n - r] * inv[r] % mod
(fac, inv) = modfac(300000, mod)
(n, k) = map(int, stdin.readline().split())
s = list(map(int, stdin.readline().split()))
ra = [None] * n
for i in range(n):
	ra[s[i]] = i
eq = 0
for i in range(n - 1):
	if s[i] + 1 == n:
		eq += 1
	elif s[i + 1] + 1 == n:
		pass
	elif ra[s[i] + 1] < ra[s[i + 1] + 1]:
		eq += 1
print(eq, file=sys.stderr)
ans = 0
for neq in range(eq + 1):
	usealp = n - neq
	if usealp > k:
		continue
	else:
		ans += modnCr(eq, neq) * modnCr(k, usealp)
		ans %= mod
print(ans)


import os, sys
from io import BytesIO, IOBase
from math import ceil
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
mod = 998244353

def pw(x, y):
	ans = 1
	while y:
		if y % 2:
			ans *= x
			y -= 1
			ans %= mod
		else:
			x *= x
			y //= 2
			x %= mod
	return ans

def ncr(n, r):
	ans = 1
	for i in range(r):
		ans *= n - i
		ans *= pw(i + 1, mod - 2)
		ans %= mod
	return ans % mod

def solve():
	n = len(a)
	if n == 0:
		return 0
	a1 = [0 for i in range(n + 1)]
	for i in range(n):
		a1[1 + i] = a[i]
	p = [0 for i in range(n + 1)]
	for i in range(n + 1):
		p[a1[i]] = i
	k = 1
	for i in range(n, 1, -1):
		if p[a1[i] + 1] <= p[a1[i - 1] + 1]:
			k += 1
	return k
(n, m) = map(int, input().split())
a = list(map(int, input().split()))
t = solve()
if m < t:
	print(0)
else:
	c = m - t
	ans = ncr(n + c, c) % mod
	print(ans)


import sys
input = sys.stdin.buffer.readline
mod = 998244353
(n, k) = map(int, input().split())
s = list(map(int, input().split()))
pos = [-1] * (n + 1)
for i in range(n):
	pos[s[i]] = i
increases = 0
for i in range(n - 1):
	increases += pos[s[i] + 1] > pos[s[i + 1] + 1]
numerator = denominator = 1
for i in range(1, n + 1):
	numerator = numerator * (k - 1 - increases + i) % mod
	denominator = denominator * i % mod
print(numerator * pow(denominator, mod - 2, mod) % mod)


import sys
input = sys.stdin.readline
mod = 998244353
(n, k) = map(int, input().split())
A = list(map(int, input().split()))
rank = [0] * (n + 1)
for (i, a) in enumerate(A):
	rank[a] = i
rank[n] = -1
cnt = 0
for i in range(n - 1):
	if rank[A[i] + 1] > rank[A[i + 1] + 1]:
		cnt += 1
(x, y) = (1, 1)
for i in range(n):
	x = x * (n - 1 + k - cnt - i) % mod
	y = y * (i + 1) % mod
print(x * pow(y, mod - 2, mod) % mod)


import sys
input = sys.stdin.readline
(n, k) = map(int, input().split())
S = list(map(int, input().split()))
mod = 998244353
FACT = [1]
for i in range(1, 5 * 10 ** 5 + 1):
	FACT.append(FACT[-1] * i % mod)
FACT_INV = [pow(FACT[-1], mod - 2, mod)]
for i in range(5 * 10 ** 5, 0, -1):
	FACT_INV.append(FACT_INV[-1] * i % mod)
FACT_INV.reverse()

def Combi(a, b):
	if 0 <= b <= a:
		return FACT[a] * FACT_INV[b] % mod * FACT_INV[a - b] % mod
	else:
		return 0
S_INV = [0] * n
for i in range(n):
	S_INV[S[i]] = i
S_INV.append(-1)
B = [0] * n
BX = 0
for i in range(1, n):
	if S_INV[S[i] + 1] < S_INV[S[i - 1] + 1]:
		B[i] += 1
		BX += 1
if k - 1 < BX:
	print(0)
else:
	c = k - 1 - BX
	print(Combi(n + c, c))


import sys
input = lambda : sys.stdin.readline().rstrip()
P = 998244353
nn = 404040
fa = [1] * (nn + 1)
fainv = [1] * (nn + 1)
for i in range(nn):
	fa[i + 1] = fa[i] * (i + 1) % P
fainv[-1] = pow(fa[-1], P - 2, P)
for i in range(nn)[::-1]:
	fainv[i] = fainv[i + 1] * (i + 1) % P
C = lambda a, b: fa[a] * fainv[b] % P * fainv[a - b] % P if 0 <= b <= a else 0
(N, K) = map(int, input().split())
A = [int(a) for a in input().split()]
B = [-1] * (N + 1)
for (i, a) in enumerate(A):
	B[a] = i
c = 0
for i in range(1, N):
	if B[A[i] + 1] < B[A[i - 1] + 1]:
		c += 1
print(C(N + K - c - 1, N))


MOD = 998244353
(n, k) = map(int, input().split())
arr = list(map(int, input().split()))
pos = [-1] * (n + 1)
for (i, a) in enumerate(arr):
	pos[a] = i
pos[-1] = -1
for i in range(n - 1):
	if pos[arr[i] + 1] < pos[arr[i + 1] + 1]:
		k += 1
if k < n:
	print(0)
else:
	fact = [1]
	for i in range(1, k + 1):
		fact.append(fact[-1] * i % MOD)
	print(fact[k] * pow(fact[n], MOD - 2, MOD) * pow(fact[k - n], MOD - 2, MOD) % MOD)


(n, k) = map(int, input().split())
p = list(map(int, input().split()))
pos = [-1] * (n + 1)
for (i, x) in enumerate(p):
	pos[x] = i
d = 0
for i in range(n - 1):
	if pos[p[i + 1] + 1] < pos[p[i] + 1]:
		d += 1
if k <= d:
	print(0)
	exit()
mod = 998244353

def modpow(x, p):
	res = 1
	while p:
		if p % 2:
			res = res * x % mod
		x = x * x % mod
		p //= 2
	return res

def C(N, K):
	num = 1
	den = 1
	for j in range(K):
		num *= N - j
		num %= mod
		den *= K - j
		den %= mod
	return num * modpow(den, mod - 2) % mod
k -= 1
ans = C(n + k - d, n)
print(ans)