← 返回题目列表

AtCoder · abc267_g

G. 增加K倍

中文机器翻译题面 查看原题

分数: 600 点

问题陈述

给你一个整数序列 A = (A_1, \dots, A_N) 长度 N.

求模数 998244353,排列 P = (P_1, \dots, P_N) of (1, 2, \dots, N) 这样:

  • 完全存在 K 整数 i 之间 1 和 (N-1) (含)使得 A_{P_i} \lt A_{P_{i + 1}}.

约束

  • 2 \leq N \leq 5000
  • 0 \leq K \leq N - 1
  • 1 \leq A_i \leq N \, (1 \leq i \leq N)
  • 输入中的所有值都是整数。

输入

输入由标准输入按以下格式给出:

N K
A_1 \ldots A_N

输出

打印答案。


示例输入 1

4 2
1 1 2 2

示例输出 1

4

四种排列满足条件: P = (1, 3, 2, 4), (1, 4, 2, 3), (2, 3, 1, 4), (2, 4, 1, 3).


示例输入 2

10 3
3 1 4 1 5 9 2 6 5 3

示例输出 2

697112