题目背景

14:27 添加了 T2 样例解释。

题目描述

给你一个序列 $a$，你可以进行不超过 $k$ 次「落笔」操作，每次选择一个 $p(1\le p\le n)$ 使得 $a_p \gets a_p +1$（即让 $a$ 中的第 $p$ 项加上 $1$），求出让 $a$ 为非负公差的等差数列的最终序列可能的情况数。

输入格式

第一行两个整数 $n,k$。

第二行 $n$ 个整数，表示序列 $a$。

输出格式

一行一个整数，表示答案。

5 6
1 2 3 4 5

2

提示

样例解释

共 $(1,2,3,4,5),(2,3,4,5,6)$，$2$ 种。

数据范围

对于 $100\%$ 的数据，$1 \le n,a_i \le 10^6$，$k\le 10^7$。

本题采用捆绑测试。

• Subtask 1(20pts)：$n,k \le 100$。
• Subtask 2(15pts)：$n \le 100$。
• Subtask 3(15pts)：$k \le 10^5$。
• Subtask 4(50pts)：无特殊限制。