← 返回题目列表

Codeforces · 958/F3

F3. 光剑(硬)

中文机器翻译题面 查看原题

银河参议院曾经发生过骚乱。数千个太阳系已宣布打算离开共和国。但不要害怕!海蒂大师成功选拔了恢复银河和平的绝地武士。然而,她知道邪恶永不眠,有一天她可能需要挑选另一群绝地武士。她想确保她有足够的选择来做到这一点。

有 n 个绝地武士,每个人都拥有 m 个颜色之一的光剑。给定数字 k,计算某些 k 个绝地武士可能拥有的 k 个不同颜色的光剑集合的数量。拥有相同颜色光剑的绝地武士是无法区分的(重要的不是人,而是光剑的颜色!),而且他们的顺序并不重要;也就是说,当且仅当每种颜色的光剑数量向量(就像在简单版本和中等版本中给出的那样)不同时,我们认为绝地武士的两个集合是不同的。我们计算所有子集,而不仅仅是输入序列的连续子段。输出对 1009 取模的答案。

输入

输入的第一行包含 n (1 ≤ n ≤ 2·105)、m (1 ≤ m ≤ n) 和 k (1 ≤ k ≤ n)。第二行包含 {1, 2, ..., m} 范围内的 n 个整数,表示后续绝地武士的光剑颜色。

输出

输出一个数字:k个光剑的不同颜色集合的数量模1009。

示例

输入 #1

4 3 2
1 2 3 2

输出 #1

4