31861번 - 비밀번호 만들기

문제

혜민이는 자신만의 규칙으로 비밀번호를 만들어내고 싶다. A부터 Z까지 순서대로 1ドル$부터 26ドル$까지 번호를 지정했을 때, 알파벳 사이의 거리는 알파벳 번호의 차이이다. 혜민이는 $M$ 자리의 비밀번호를 만든다면 몇 개를 만들 수 있는지 알고 싶다. 비밀번호를 만드는 규칙은 다음과 같다.

• 2ドル$ 이상 $M$ 이하의 정수 $i$에 대해, $i - 1$번째 알파벳과 $i$번째 알파벳 사이의 거리가 $N$ 이상이 되도록 한다.
• 알파벳은 대문자만 사용한다.
• 알파벳은 중복으로 사용이 가능하다.

예를 들어, $N=24,ドル $M=4$인 경우, 첫 번째 알파벳이 A이면 AYAY, AYAZ, AZAY, AZAZ, AZBZ를, Z이면 ZAYA, ZAZA, ZAZB, ZBZA, ZBZB를, B이면 BZAY, BZAZ, BZBZ를, Y이면 YAYA, YAZA, YAZB를 만들 수 있다. 따라서 5ドル+5+3+3$으로 총 16ドル$개의 비밀번호를 만들 수 있다.

만들 수 있는 비밀번호의 개수를 1ドル ,円 000 ,円 000 ,円 007 \left(=\ 10^9 + 7 \right)$로 나눈 나머지를 출력해 보자.

입력

첫째 줄에 정수 $N(0 \leq N \leq 25)$과 $M(2 \leq M \leq 1 ,円 000)$이 공백으로 구분되어 주어진다.

출력

만들 수 있는 비밀번호의 개수를 1ドル ,円 000 ,円 000 ,円 007$로 나눈 나머지를 출력한다.

제한

힌트