회문 끝말잇기

https://www.acmicpc.net/problem/30641

이 문제의 핵심을 요약하면 다음과 같다.

1. 게임 규칙
   • 길이가 $L$ 이상 $U$ 이하인 영어 알파벳($A$부터 $Z$까지)으로만 이루어진 회문(앞에서 읽으나 뒤에서 읽으나 동일한 문자열)만을 사용하여 끝말잇기를 진행한다.
   • 호영이가 선공으로 시작하며, 이후 두 사람은 항상 승리를 위해 최선의 수를 둔다.
   • 이미 사용된 단어는 다시 사용할 수 없다.
2. 회문의 성질
   • 회문은 첫 글자와 마지막 글자가 동일하다.
   • 따라서 첫 번째로 골라진 회문의 첫 글자(=마지막 글자)에 따라 이후 모든 단어는 동일한 알파벳으로 시작·끝나야 한다.
   • 예를 들어, ‘EYE’를 첫 단어로 선택했다면 이후에는 모두 ‘E…E’ 형태의 회문만 사용할 수 있다.
3. 출력
   1. 첫 줄에 승자: 호영이가 이기면 H, 아란이가 이기면 A
   2. 둘째 줄에 실제 게임에서 사용된 단어의 총 개수(=첫 번째로 고른 알파벳으로 만들 수 있는 회문의 총 개수)를 $10^9+7$로 나눈 나머지
4. 결론
   • “길이 $L$에서 $U$ 사이에 속하는 회문을, 시작·끝이 같은 한 글자 $c$에 대해 만들 수 있는 총 개수”를 구하여 그 값의 홀짝 여부로 승패가 결정된다.
   • 실제 사용된 단어 수(=그 알파벳으로 가능한 회문 전체 개수)는 10^9+7로 나눈 값을 출력한다.