公式解説の \(f(x)\) を求めます。

LGV 公式の利用

右向きまたは上向きにのみ移動できる格子グラフを考えます。各 \(i\) に対して、始点 \(S_i=(i,-i)\) と終点 \(T_i=(x_i,1-i)\) を用意します。

\(S_i\) から \(T_i\) へ移動する経路は、右向きに \(x_i-i\) 回、上向きにちょうど \(1\) 回移動します。この上向きの一回の \(x\) 座標を \(a_i\) とすると、\(i\le a_i\le x_i\) です。

隣り合う経路を考えます。\(S_i\) から出る経路は、高さ \(-i\) 上を \(x=i\) から \(x=a_i\) まで進みます。一方、\(S_{i+1}\) から出る経路は、高さ \(-i\) 上を \(x=a_{i+1}\) から右へ進みます。よって、交わらないための条件は \(a_i<a_{i+1}\) です。よって「互いに交わらない経路族」と「条件を満たす列 \(a\) 」が \(1\) 対 \(1\) に対応します。

\(S_j\) から \(T_i\) への経路数は \(\displaystyle A_{i,j}=\binom{x_i-i+1}{j-i+1}\) であることを踏まえれば LGV 公式より、求めるものは下式です。

\[ \operatorname{count}(x) = \det\left[ \binom{x_i-i+1}{j-i+1} \right]_{1\le i,j\le K} \]

行列式を求める

行列 \(A\) の成分を見ると、\(j<i-1\) なら \(A_{i,j}=0\) であり、\(j=i-1\) なら

\[ A_{i,i-1}=\binom{x_i-i+1}{0}=1 \]

です。よって、\(A\) は副対角成分がすべて \(1\) である上ヘッセンベルグ行列です。このとき、余因子が簡単な形になります。

\(D_i\) を、\(i\) 行目・\(i\) 列目以降からなる小行列の行列式とします。便宜的に \(\det(D_{K+1}) = 1\) とします。

この \(D_i\) の先頭行を余因子展開します。\(j\) 列目を選んだとき、残る行列は、

\[\begin{pmatrix} B & *\\ 0 & D_{j+1} \end{pmatrix} \]

で \(B\) は対角成分がすべて \(1\) の上三角行列です。

したがって、

\[ \det(D_i) = \sum_{j=i}^{K} (-1)^{j-i} \binom{x_i-i+1}{j-i+1} \det(D_{j+1}) \]

となります。求める個数は \(\det(D_1)\) です。

固定した \(i\) に対して二項係数の下側は \(1,2,\ldots,K-i+1\) と連続しているので、

\[ \binom{n}{r} = \binom{n}{r-1}\frac{n-r+1}{r} \]

を使って、それぞれ \(O(1)\) で更新できます。したがって、全体を \(O(K^2)\) で計算できます。

実装

mod = 998244353

n, k = map(int, input().split())
x = list(map(int, input().split()))

inv = [0] * (k + 1)
for i in range(1, k + 1):
    inv[i] = pow(i, mod - 2, mod)

def calc(x):
    k = len(x)
    dp = [0] * (k + 1)
    dp[k] = 1

    for i in range(k - 1, -1, -1):
        n = x[i] - i
        comb = 1
        v = 0

        for j in range(i, k):
            r = j - i + 1
            comb *= n - r + 1
            comb %= mod
            comb *= inv[r]
            comb %= mod

            t = comb * dp[j + 1] % mod

            if (j - i) % 2 == 0:
                v += t
            else:
                v -= t

        dp[i] = v % mod

    return dp[0]


tmp = 1
for i in range(1, k + 1):
    tmp = tmp * (n + 1 - i) % mod 
    tmp = tmp * inv[i] % mod

mini = calc(x)
maxi = (tmp - calc([n+1-v for v in reversed(x)]) + 1) % mod

print(mini, maxi)