CF958F3 Lightsabers (hard)

银河参议院曾经动荡不安。数千个恒星系宣布打算脱离共和国。但不用担心！Heidi 大师成功地挑选出了恢复银河和平的绝地武士。然而，她知道邪恶永不眠，总有一天她可能需要再次挑选一组绝地武士。她希望确保自己有足够的选择。 现在有 $n$ 名绝地武士，每人拥有一把 $m$ 种颜色之一的光剑。给定一个数字 $k$，请计算可能由 $k$ 名绝地武士组成的、颜色各异的 $k$ 把光剑的不同组合数。拥有相同颜色光剑的绝地武士是不可区分的（关键在于光剑颜色，而不是武士本人！），并且顺序无关；也就是说，只有当每种颜色光剑的数量向量不同（就像你在简单版和中等版中看到的那样），我们才认为两组绝地武士的组合是不同的。我们统计所有子集，而不仅仅是输入序列的连续子段。请输出答案对 $1009$ 取模后的结果。

第一行包含 $n$（$1 \leq n \leq 2 \cdot 10^{5}$）、$m$（$1 \leq m \leq n$）和 $k$（$1 \leq k \leq n$）。 第二行包含 $n$ 个整数，范围为 $1,2,\ldots,m$，表示每位绝地武士的光剑颜色。

输出一个整数，表示不同颜色组合的 $k$ 把光剑的方案数，对 $1009$ 取模。

由 ChatGPT 4.1 翻译