{"trustable":true,"sections":[{"title":"","value":{"format":"MD","content":"It\u0027s Alan\u0027s birthday. He is looking for balloons to decorate his house. He visits a shop which has many coloured balloons numbered $1$ to $n$ arranged in a row. The colour of each balloon can be represented as an integer between $1$ and $n$. Alan only wants to pick up a **contiguous subsequence** of these balloons. However, the total cost of a set of balloons is calculated in a strange way: $\\sum_{i\u003d1}^{n} cnt_i^k$ where $cnt_i$ is the number of balloons of $i^{th}$ colour in the set.\r\n\r\nFind the total cost of all possible sets of balloons that can be bought by Alan. Two sets of balloons are considered different if there is a balloon numbered $i$ which is present in one set but not in the other. Since the answer can be huge, output the value modulo $10^9+7$.\r\n\r\n### Input\r\n- The first line of the input consists of two integers $n$ and $k$. The next line consists of $n$ integers where the $i^{th}$ integer denotes the colour of the balloon numbered $i$.\r\n\r\n### Output\r\nFor each test case, print a single line containing one integer: total cost modulo $10^9+7$.\r\n\r\n### Constraints \r\n- $1 \\le n, k \\le 200000$\r\n\r\n### Example Input\r\n```\r\n3 2\r\n1 2 1\r\n```\r\n\r\n### Example Output\r\n```\r\n12\r\n```\r\n\r\n### Explanation\r\nAlan can buy the following sets of balloons:\r\n$(1)$, $(2)$, $(3)$ with cost $1$ each;\r\n$(1,2)$, $(2,3)$ with cost $2$ each;\r\n$(1,2,3)$ with cost $5$.\r\n\r\nHence the total cost is $12$.\r\n"}}]}