Hasan and boring classes
All submissions for this problem are available.
Read problems statements in Mandarin chinese, Russian and Vietnamese as well.
Hasan is a computer science student, he likes his study field, especially programming and algorithms, but he doesn’t like attending classes at all since they are very boring, especially that the quality of education in his college is extremely low, but sometimes he is forced to attend in order to maintain his attendance rate otherwise he will be prevented from doing final exams!
Currently Hasan is attending `communication skills` class and he is now feeling very bored especially that he thinks such course should not belong to a computer science program, luckily he remembered a problem that one of his friends has given him so he decided to spend the time thinking about it, the problem states:
Given a string S of length N of lower English letters, find how many strings T exists of length N of lower English letters such that T is palindrome and hamming distance between T and S is at most K. since the answer is large find the remainder modulo 109 + 7
Since you also don’t like `communication skills` classes you decided to solve this problem too.
The first line of the input contains an integer T denoting the number of test cases.
each test-case is described with two lines, the first line of each test-case contains two integers N and K.
The second line of each test-case will contains the string S of length N.
For each test case, output a single line containing the answer to the test-case.
- 1 ≤ T ≤ 10,000
- 1 ≤ N ≤ 300,000
- 1 ≤ sum of N in all test-cases ≤ 1,000,000
- 0 ≤ K ≤ N
- String S will consist of English lower letters.
Input: 2 3 2 abc 3 1 abc Output: 76 2
in second test-case the only possible strings are "aba" and "cbc"
|Tags||combinatorics, cook88, kingofnumbers, kingofnumbers, likecs, medium|
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, 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, PERL6, TEXT, SCM chicken, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.