팰린드롬 문자열의 개수

팰린드롬은 왼쪽에서 읽은 결과와 오른쪽에서 읽은 결과가 같은 문자열이다. 이 문제에서는 팰린드롬 여부를 판단할 때 공백을 모두 무시한다.

서로 다른 단어 N개가 주어진다. 이 단어들을 골라 순서대로 나열해 문자열 S를 만들 수 있다. 같은 단어를 여러 번 사용할 수 있고, 사용하지 않는 단어가 있어도 된다. 단어와 단어 사이에는 공백을 정확히 하나 넣어야 하며, 같은 단어를 연속해서 사용할 때도 공백을 넣어야 한다. S는 공백으로 시작하거나 끝날 수 없다.

만들 수 있는 문자열 S 중에서, 공백을 무시하면 팰린드롬이고 전체 길이가 K 이하인 문자열의 개수를 구하라. 길이를 셀 때는 단어 사이의 공백도 포함한다. 빈 문자열은 세지 않는다.

첫째 줄에 단어의 개수 N과 길이 제한 K가 주어진다. N은 50 이하, K는 100 이하인 자연수이다.

다음 N개의 줄에는 단어가 한 줄에 하나씩 주어진다. 각 단어는 알파벳 소문자로만 이루어져 있고 길이는 15 이하이며, 같은 단어는 두 번 주어지지 않는다.

조건을 만족하는 문자열 S의 개수를 835454957로 나눈 나머지를 출력한다.

첫 번째 공개 테스트 케이스에서는 길이 제한 안에서 조건을 만족하는 문자열이 5개 존재한다.