Given a string S, consisting of lowercase alphabets only. Your task is to find number of subsequence that are palindrome and has sum equal to K.
You can take value of "a" as 0, "b" as 1, "c" as 2 and so on for calculation of the sum.

Input
String S
Integer K

Output
A single Integer

Constraints
1 <= Length of String <=36
0 <= K <= 900