목표 지점으로
시간 제한1초메모리 제한512 MB
2N+M 칸을 정확히 도달하도록 2칸 이동 N번과 1칸 이동 M번을 배열하되, 2칸 이동이 세 번 연속 나오지 않는 경우의 수를 1e9+7로 나눈 나머지를 구한다.
문제
Ani는 말 하나와 개의 칸으로 이루어진 게임을 하고 있다. 칸은 부터 까지 번호가 붙어 있다. 말은 처음에 칸 에 있다. Ani는 슈퍼 카드 장과 일반 카드 장을 가지고 있다.
한 턴에 Ani는 아직 사용하지 않은 카드 한 장을 사용할 수 있다. 일반 카드를 사용하면 말은 한 칸 앞으로 이동한다. 즉 칸 에서 칸 로 간다. 슈퍼 카드를 사용하면 말은 두 칸 앞으로 이동한다. 즉 칸 에서 칸 로 간다. Ani는 슈퍼 카드를 연속한 세 턴에 사용할 수 없다.
턴이 끝난 뒤 말은 목표인 칸 에 있어야 한다. Ani는 말이 목표까지 이동할 수 있는 경로의 수가 궁금하다. 같은 턴 수가 지난 뒤 말이 다른 칸에 있으면 두 경로는 다른 경로로 본다.
예를 들어 , 이면 Ani의 말이 목표까지 이동할 수 있는 경로는 두 가지다.
- 둘째 턴에 일반 카드를 사용하고, 첫째, 셋째, 넷째 턴에 슈퍼 카드를 사용한다.
- 셋째 턴에 일반 카드를 사용하고, 첫째, 둘째, 넷째 턴에 슈퍼 카드를 사용한다.
첫째 턴에 일반 카드를 사용하면 마지막 세 턴에 슈퍼 카드를 연속해서 사용해야 하므로, 첫째 턴에 일반 카드를 사용하는 경로는 없다.
입력
입력의 첫째 줄에 두 정수 이 주어진다. () 은 슈퍼 카드의 수, 은 일반 카드의 수다.
출력
Ani의 말이 목표까지 이동할 수 있는 경로의 수를 한 줄에 출력한다. 값이 클 수 있으므로 로 나눈 나머지를 출력한다.