不算很难的题目，但是需要一些基本的思考。

我们看到这玩意就知道一个事情：值域限制要求的上界，而我们这个 \(a_i > a_{i + 1}\) 是一个对下界的限制，这不太好，我们不妨容斥一下，将这个限制变成钦定 \(k - 1\)

个的不降相邻元素对，容斥写一个二项式反演一样的东西即可。

考察这玩意怎么做，本质上是若干个钦定的极长不降序列拼在一起，那么你设 \(g_{i, j}\) 表示要 \([i, j]\)

变为不降的方案数，再用容斥跑一个区间 DP（这是简单的），写个朴素 DP 转移一下即可。