{"problem":{"name":"F3. Lightsabers (hard)","description":{"content":"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 ","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":4000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF958F3"},"statements":[{"statement_type":"Markdown","content":"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.\n\nThere 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\n## Input\n\nThe 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\n## Output\n\nOutput one number: the number of differently colored collections of _k_ lightsabers modulo 1009.\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"银河议会曾一度动荡不安，数千个恒星系统宣布意图脱离共和国。但不必担心！海迪大师成功选出了恢复银河和平的绝地武士。然而，她深知邪恶永不眠息，终有一日她需要再次挑选另一组绝地武士。她希望确保自己有足够的选择余地。\n\n现有 #cf_span[n] 位绝地武士，每人持有一把颜色属于 #cf_span[m] 种之一的光剑。给定一个数 #cf_span[k]，请计算某些 #cf_span[k] 位绝地武士可能拥有的、颜色互不相同的光剑集合的数量。持有相同颜色光剑的绝地武士是不可区分的（重要的是光剑的颜色，而非本人！），且顺序无关；也就是说，我们仅当两个集合中每种颜色光剑的数量向量（如你在简单版和中等版中所见）不同时，才认为它们是不同的。我们统计所有子集，而不仅是输入序列中的连续子段。请输出答案对 #cf_span[1009] 取模的结果。\n\n输入的第一行包含 #cf_span[n] (#cf_span[1 ≤ n ≤ 2·105])、#cf_span[m] (#cf_span[1 ≤ m ≤ n]) 和 #cf_span[k] (#cf_span[1 ≤ k ≤ n])。第二行包含 #cf_span[n] 个整数，范围为 #cf_span[{1, 2, ..., m}]，表示后续绝地武士所持光剑的颜色。\n\n## Input\n\n输入的第一行包含 #cf_span[n] (#cf_span[1 ≤ n ≤ 2·105])、#cf_span[m] (#cf_span[1 ≤ m ≤ n]) 和 #cf_span[k] (#cf_span[1 ≤ k ≤ n])。第二行包含 #cf_span[n] 个整数，范围为 #cf_span[{1, 2, ..., m}]，表示后续绝地武士所持光剑的颜色。\n\n## Output\n\n输出一个数：对 #cf_span[1009] 取模后的、#cf_span[k] 把光剑的颜色互不相同的集合数量。\n\n[samples]","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ n, m, k \\in \\mathbb{Z}^+ $ with $ 1 \\leq k \\leq n $, $ 1 \\leq m \\leq n $.  \nLet $ c = (c_1, c_2, \\dots, c_m) \\in \\mathbb{Z}_{\\geq 0}^m $ be the frequency vector of lightsaber colors, where $ c_j $ is the number of Jedi Knights with lightsaber of color $ j $, for $ j = 1, \\dots, m $.  \nLet $ \\mathcal{C} = \\left\\{ (x_1, \\dots, x_m) \\in \\mathbb{Z}_{\\geq 0}^m \\,\\middle|\\, \\sum_{j=1}^m x_j = k,\\, 0 \\leq x_j \\leq c_j \\text{ for all } j \\right\\} $.\n\n**Constraints**  \n1. $ 1 \\leq n \\leq 2 \\cdot 10^5 $  \n2. $ 1 \\leq m \\leq n $  \n3. $ 1 \\leq k \\leq n $  \n4. Each input color is in $ \\{1, 2, \\dots, m\\} $, so $ \\sum_{j=1}^m c_j = n $\n\n**Objective**  \nCompute  \n$$\n|\\mathcal{C}| \\mod 1009\n$$  \ni.e., the number of non-negative integer solutions $ (x_1, \\dots, x_m) $ to  \n$$\n\\sum_{j=1}^m x_j = k, \\quad \\text{with } 0 \\leq x_j \\leq c_j \\text{ for all } j\n$$  \nmodulo $ 1009 $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF958F3","tags":["fft"],"sample_group":[["4 3 2\n1 2 3 2","4"]],"created_at":"2026-03-03 11:00:39"}}