lukamosiashvili's blog

By lukamosiashvili, 2 months ago, , Is there any EJOI mirror?

By lukamosiashvili, 13 months ago, , I wrote one my problem in my blog: http://codeforces.com/blog/entry/61556 , this problem is with difficult D2B-D1A. now I will write the problem with difficult D1A(maybe this is with other difficult).

time limit: 2 seconds

memory limit: 256 megabytes

there is given a string s. the substring is named half-palindrome if we can do palindrome with change some places of characters(we can do not change this substring). find the number of substrings of s that are half-palindromes(the substring must not be empty).

the length of string is at most 100 000 and all characters are in lower-case and are one of the first 10 characters in alphabet.

example test case:

input:

aac

output:

5

how to solve it?

I know this but I can not write that because for me is hard speak English. write in comments solution of this task. I hope you enjoyed with solving this task and this blog was usefull for you :). By lukamosiashvili, history, 14 months ago, , ian have secuence A of n numbers . ian wroted on a paper all subsecuences of A that length are k. then he wrote the product of numbers for each subsequence on his albom. then he wrote a sum of numbers from albom on a table. what number is on table? for example if n=3 k=2 and subsequence is (2,4,5) on the paper will be: (2,4) (2,5) (4,5) subsequences, in albom numbers: 8 10 20. on a table 8+10+20=38; if n=3 k=1 and subsequence is (2,4,5) answer is: 2+4+5=11;

Input Format

in a first line two integer numbers, n and k in a next line is the secuence A. each element is positive integer that is not grater than 1 000 000 000;

Constraints

1≤n≤100 000; 1≤k≤min(n,20); all numbers of sequance A are positive integers that are not grater than 1 000 000 000;

Output Format

print the number on table with modulo 10^9+7;

Sample Input 0

3 2

2 4 5

Sample Output 0

38

Explanation 0

if n=3 k=2 and subsequence is (2,4,5) on the paper will be: (2,4) (2,5) (4,5) subsequences, in albom numbers: 8 10 20. on a table 8+10+20=38;

Sample Input 1

3 1

2 4 5

Sample Output 1

11

Explanation 1

if n=3 k=1 and subsequence is (2,4,5) answer is: 2+4+5=11; 