30641번 - 회문 끝말잇기

문제

회문이란 앞에서부터 읽으나 뒤에서부터 읽으나 똑같은 문자열이다. 예를 들어 “MADAM”, “RACECAR”, “K”는 회문이고, “MAMA”, “IGRUS”는 회문이 아니다.

호영이와 아란이가 영어로 회문 끝말잇기를 하려고 한다. 사전에 없는 단어라도 영어 알파벳(A, B, C, ..., Z의 총 26가지 문자)으로 구성된 회문이기만 하면 사용할 수 있다. EYE → ECWWCE → EEVEE → ... 물론 이러면 게임이 영원히 끝나지 않으므로, 길이가 L이상 U이하인 회문만 사용하기로 했다.

게임은 호영이가 먼저 시작하며, 둘은 항상 회문 끝말잇기에서 승리하기 위해 최선을 다한다. 게임이 끝난 뒤 승자는 누구인지, 사용된 단어는 총 몇 개인지 알아보자.

입력

한 개의 줄에 두 정수 L과 U가 공백을 구분으로 주어진다.

출력

첫째 줄에 호영이가 이긴다면 H를, 아란이가 이긴다면 A를 출력한다.

둘째 줄에 게임에서 사용된 단어의 개수를 10⁹ + 7로 나눈 나머지를 출력한다.

제한

• 1 ≤ L ≤ U ≤ 10⁶

힌트