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