팰린드롬 단어 이어 붙이기

앞에서 읽어도 뒤에서 읽어도 같은 문자열을 팰린드롬이라고 한다.

서로 다른 영어 단어 N개가 주어진다. 이 단어들을 원하는 순서로 이어 붙여 전체 길이가 L인 팰린드롬을 만드는 방법의 수를 구하라.

각 단어는 여러 번 사용할 수 있다. 선택한 단어들의 나열이 다르면, 이어 붙인 최종 문자열이 같더라도 서로 다른 방법으로 센다.

첫째 줄에 단어의 개수 N이 주어진다. 둘째 줄에 만들 문자열의 길이 L이 주어진다. 다음 N개 줄에는 서로 다른 영어 단어가 한 줄에 하나씩 주어진다.

• 1 <= N <= 50
• 1 <= L <= 30
• 각 단어의 길이는 1 이상 15 이하이다.
• 모든 단어는 영어 대문자로만 이루어진다.

주어진 단어를 이어 붙여 길이가 L인 팰린드롬을 만드는 방법의 수를 출력한다. 정답은 2,100,000,000을 넘지 않는다.