CF958F3.Lightsabers (hard)

There used to be unrest in the Galactic Senate. Several thousand solar systems had declared their intentions to leave the Republic. But fear not! Master Heidi was able to successfully select the Jedi Knights that have restored peace in the galaxy. However, she knows that evil never sleeps and a time may come when she will need to pick another group of Jedi Knights. She wants to be sure she has enough options to do so.

There are n Jedi Knights, each of them with a lightsaber of one of m colors. Given a number k, compute the number of differently colored collections of k lightsabers that some k Jedi Knights might have. Jedi Knights with lightsabers of the same color are indistinguishable (it's not the person, it's the lightsaber color that matters!), and their order does not matter; that is, we consider two collections of Jedi Knights to be different if and only if their vectors of counts of lightsabers of each color (like what you were given in the easy and the medium versions) are different. We count all subsets, not only contiguous subsegments of the input sequence. Output the answer modulo 1009.

银河议会曾经动荡不安，数千个恒星系统宣布意图脱离共和国。但请不必担心！绝地大师海蒂成功地挑选出了一批绝地武士，从而恢复了银河系的和平。然而，她深知邪恶永不停歇，未来某一天她或许需要再次挑选另一批绝地武士。她希望确保自己拥有足够多的备选方案。

共有 $n$ 名绝地武士，每人持有一把颜色为 $m$ 种颜色之一的光剑。给定一个整数 $k$，请计算：由某 $k$ 名绝地武士所持有的、颜色组合互不相同的光剑集合的总数。持有相同颜色光剑的绝地武士彼此不可区分（关键在于光剑的颜色，而非武士本人），且集合中武士的顺序无关紧要；即，我们仅当两个绝地武士集合在每种颜色光剑数量上的计数向量（如“简单版”与“中等版”题目中所给定的）不同时，才认为它们是不同的集合。我们统计的是所有可能的子集（而非输入序列中仅连续的子段）。请将答案对 $1009$ 取模后输出。

The first line of the input contains n (1 ≤ n ≤ 2·105), m (1 ≤ m ≤ n) and k (1 ≤ k ≤ n). The second line contains n integers in the range {1, 2, ..., m} representing colors of the lightsabers of subsequent Jedi Knights.

输入的第一行包含三个整数 $n$（$1 ≤ n ≤ 2·10^5$）、$m$（$1 ≤ m ≤ n$）和 $k$（$1 ≤ k ≤ n$）。第二行包含 $n$ 个整数，取值范围为 $\{1, 2, ..., m\}$，表示依次排列的绝地武士所持光剑的颜色。

Output one number: the number of differently colored collections of k lightsabers modulo 1009.

输出一个数字：恰好由 k 把光剑组成的、颜色互不相同的集合的个数，对 1009 取模。