{"trustable":true,"sections":[{"title":"","value":{"format":"MD","content":"今天是Alan的生日。他想要气球来装饰他的房子。他去了一家商店,商店里有很多彩色的气球,编号从$1$到$n$排成一排。每个气球的颜色可以用介于$1$和$n$之间的整数表示。Alan只想挑选这些气球中的**连续子序列**。然而,一组气球的总成本是以一种奇怪的方式计算的: $\\sum_{i\u003d1}^{n} cnt_i^k$,其中$cnt_i$是该组中$i^{th}$颜色的气球数量。\n\n找出Alan可以购买的所有可能气球组合的总成本。如果一个气球组合中存在一个编号为$i$的气球,而另一个组合中没有,则认为这两个组合是不同的。由于答案可能很大,输出取模$10^9+7$的值。\n\n### 输入\n- 输入的第一行包含两个整数$n$和$k$。接下来一行包含$n$个整数,其中第$i^{th}$个整数表示编号为$i$的气球的颜色。\n\n### 输出\n对于每个测试用例,输出一行包含一个整数: 取模$10^9+7$后的总成本。\n\n### 约束\n- $1 \\le n, k \\le 200000$\n\n### 示例输入\n```\n3 2\n1 2 1\n```\n\n### 示例输出\n```\n12\n```\n\n### 解释\nAlan可以购买以下气球组合:\n$(1)$,$(2)$,$(3)$,每个成本为$1$;\n$(1,2)$,$(2,3)$,每个成本为$2$;\n$(1,2,3)$,成本为$5$。\n\n因此总成本为$12$。"}}]}