### Problem Statement

A palindrome is a string that reads the same from left to right as it does from right to left, ignoring spaces. We are building a machine that makes the best palindromes in the world and we need you to make a function that calculates the number of possible results before trying it for the first time.

You will be given a String[] words and an int k. Each palindrome generated by the machine will be a single space separated list of words, without leading or trailing spaces, that contains at most k characters (including spaces). Each word is an element of words, and each word can be used zero or more times in each palindrome. Return the number of different palindromes that can be generated by the machine modulo 835454957.

### Definition

 Class: CountPalindromes Method: count Parameters: String[], int Returns: int Method signature: int count(String[] words, int k) (be sure your method is public)

### Notes

-Returning the answer modulo 835454957 means that you have to return the remainder of dividing the answer by 835454957.
-The empty string does not count as a palindrome.

### Constraints

-words will contain between 1 and 50 elements, inclusive.
-Each element of words will contain between 1 and 15 characters, inclusive.
-Each character of each element of words will be a lowercase letter ('a'-'z').
-No two elements of words will be equal.
-k will be between 1 and 100, inclusive.

### Examples

0)

 `{"tragic","cigar"}` `24`
`Returns: 1`
 The only palindrome with no more than 24 characters is "cigar tragic" with 12 characters. "cigar tragic cigar tragic" is also a valid palindrome, but has 25 characters.
1)

 `{"z","zz"}` `4`
`Returns: 5`
 The 5 different palindromes are (quotes for clarity): "z","zz","z z","z zz","zz z".
2)

 `{"aba","acaba","baca","cac","b","c","a"}` `70`
`Returns: 370786966`
 Remember to return the answer modulo 835454957.
3)

 `{"hello"}` `100`
`Returns: 0`
 There is no way to make a palindrome.

#### Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=7418

#### Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10661&pm=7418

soul-net

#### Testers:

PabloGilberto , brett1479 , Olexiy , Andrew_Lazarev

#### Problem categories:

Dynamic Programming