Colorful Balloons

All submissions for this problem are available.
It's Alan's 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=1}^{n} cnt_i^k$ where $cnt_i$ is the number of balloons of $i^{th}$ colour in the set. Find 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$. ### Input  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$. ### Output For each test case, print a single line containing one integer: total cost modulo $10^9+7$. ### Constraints  $1 \le n, k \le 200000$ ### Example Input ``` 3 2 1 2 1 ``` ### Example Output ``` 12 ``` ### Explanation Alan can buy the following sets of balloons: $(1)$, $(2)$, $(3)$ with cost $1$ each; $(1,2)$, $(2,3)$ with cost $2$ each; $(1,2,3)$ with cost $5$. Hence the total cost is $12$.Author:  rumblefool 
Tags  rumblefool 
Date Added:  28112019 
Time Limit:  2 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, SQL, kotlin, PERL6, TEXT, SCM chicken, PYP3, CLOJ, R, COB, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 