인터벌 트레이닝
시간 제한2초메모리 제한512 MB
k로 시작해 합이 n이 되면서 인접한 값의 대소 관계가 위아래로 번갈아 나타나는 양의 정수 수열의 개수를 10^9+7로 나눈 나머지를 구한다.
문제
체육 대학에서 선수를 위한 새로운 인터벌 트레이닝 방법을 개발했다. 이 방법에 따르면 선수는 매일 훈련해야 하지만, 부하의 증가와 감소가 번갈아 나타나야 한다.
훈련 계획은 양의 정수 수열 으로 나타내며, 는 일째 선수의 부하를 뜻한다. 인접한 두 날의 부하는 서로 달라야 한다: . 부하의 증가와 감소가 번갈아 나타나려면 부터 까지 다음 조건을 만족해야 한다: 이면 이고, 이면 이다.
계획 전체의 부하 합은 이어야 한다. 즉 이다. 계획의 일수에는 제한이 없어 은 임의로 정할 수 있지만, 첫날의 부하는 고정되어 있다: .
새 방법을 시험하기 전에 대학 측은 조건을 만족하는 훈련 계획이 몇 가지인지 알아보려 한다. 과 가 주어졌을 때 조건을 만족하는 훈련 계획의 수를 구하고, 그 수를 로 나눈 나머지를 출력하는 프로그램을 작성하라.
입력
첫째 줄에 정수 과 가 주어진다 (, ).
출력
훈련 계획의 수를 로 나눈 나머지를 한 줄에 출력한다.
힌트
첫 번째 예제에서는 다음 계획들이 조건을 만족한다: , , , .
두 번째 예제에서는 만이 조건을 만족한다.