题目描述

给你一个长度为 $n$ 的正整数序列 $T$，保证 $T$ 为严格单调递增。你需要构造如下的序列 $S$，满足：

1. $S$ 是 $T$ 的一个排列
2. $\sum\limits_{i=1}^n \min(S_i,T_i) = k$

现在你需要回答有多少种可行的 $S$ 的构造方法。答案可能很大，请输出答案对 $10^9+9$ 取模的值。

输入格式

第一行包含两个整数 $n,~k$，表示 $T$ 的长度，以及一个在题目描述中所提到的整数。

第二行有 $n$ 个整数，第 $i$ 个数表示 $T_i$。

输出格式

输出题目所求对 $10^9+9$ 取模的结果。

5 10
1 2 3 4 5

24

说明

$1\leq k\leq 2.5\times10^3,~1\leq T_i \leq 50$。

$10\%$ 的数据满足 $n \le 5$。

$50\%$ 的数据满足 $n \le 10$。

$100\%$ 的数据满足 $n \le 50$。

本题使用 Subtask。