시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 24 9 8 42.105%

문제

팰린드롬이란 왼쪽에서부터 읽을 때와 오른쪽에서부터 읽을 때가 같은 문자열을 말한다. 이 때, 공백은 무시한다.

N개의 단어가 주어진다. 이 단어를 이용해서 문자열 S를 만들 수 있다. 단어와 단어 사이에는 공백을 하나 집어 넣어야 하며, 각 단어를 여러번 사용하거나, 사용하지 않는 단어가 있어도 된다. 같은 단어를 연속해서 사용하는 경우에도 공백을 집어넣어야 한다.

이렇게 만들 수 있는 문자열 S중에서 팰린드롬이면서, 길이가 K이하인 것의 개수를 구하는 프로그램을 작성하시오. 빈 문자열은 팰린드롬이 아니다. 문자열의 길이는 공백을 포함한다. S는 공백으로 시작하거나 끝날 수 없다.

입력

첫째 줄에 단어의 개수 N과 K가 주어진다. N은 50보다 작거나 같고, K는 100보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 단어가 주어진다. 알파벳 소문자로만 구성되 있고, 길이는 최대 15이며, 중복되지 않는다.

출력

첫째 줄에 문제의 정답을 835454957로 나눈 나머지를 출력한다.

예제 입력

2 4
z
zz

예제 출력

5

예제 입력 2

7 70
aba
acaba
baca
cac
b
c
a

예제 출력 2

370786966

예제 입력 3

1 100
hello

예제 출력 3

0

예제 입력 4

2 24
tragic
cigar

예제 출력 4

1

힌트

예제 1의 경우에 만들 수 있는 단어는 다음과 같다.

z
zz
zz z
z zz
z z

출처