아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

목표 지점으로

시간 제한1초메모리 제한512 MB

요약
2N+M 칸을 정확히 도달하도록 2칸 이동 N번과 1칸 이동 M번을 배열하되, 2칸 이동이 세 번 연속 나오지 않는 경우의 수를 1e9+7로 나눈 나머지를 구한다.
난이도

보통10점 중 7점

유형
조합론, 동적 계획법, 수학, 그리디
정답자
아직 제출이 없습니다

문제

Ani는 말 하나와 2N+M+12N + M + 1개의 칸으로 이루어진 게임을 하고 있다. 칸은 00부터 2N+M2N + M까지 번호가 붙어 있다. 말은 처음에 칸 00에 있다. Ani는 슈퍼 카드 NN장과 일반 카드 MM장을 가지고 있다.

한 턴에 Ani는 아직 사용하지 않은 카드 한 장을 사용할 수 있다. 일반 카드를 사용하면 말은 한 칸 앞으로 이동한다. 즉 칸 xx에서 칸 x+1x + 1로 간다. 슈퍼 카드를 사용하면 말은 두 칸 앞으로 이동한다. 즉 칸 xx에서 칸 x+2x + 2로 간다. Ani는 슈퍼 카드를 연속한 세 턴에 사용할 수 없다.

N+MN + M턴이 끝난 뒤 말은 목표인 칸 2N+M2N + M에 있어야 한다. Ani는 말이 목표까지 이동할 수 있는 경로의 수가 궁금하다. 같은 턴 수가 지난 뒤 말이 다른 칸에 있으면 두 경로는 다른 경로로 본다.

예를 들어 N=3N = 3, M=1M = 1이면 Ani의 말이 목표까지 이동할 수 있는 경로는 두 가지다.

  1. 둘째 턴에 일반 카드를 사용하고, 첫째, 셋째, 넷째 턴에 슈퍼 카드를 사용한다.
  2. 셋째 턴에 일반 카드를 사용하고, 첫째, 둘째, 넷째 턴에 슈퍼 카드를 사용한다.

첫째 턴에 일반 카드를 사용하면 마지막 세 턴에 슈퍼 카드를 연속해서 사용해야 하므로, 첫째 턴에 일반 카드를 사용하는 경로는 없다.

입력

입력의 첫째 줄에 두 정수 NN MM이 주어진다. (1≤N,M≤100 0001 \le N, M \le 100\,000) NN은 슈퍼 카드의 수, MM은 일반 카드의 수다.

출력

Ani의 말이 목표까지 이동할 수 있는 경로의 수를 한 줄에 출력한다. 값이 클 수 있으므로 1 000 000 0071\,000\,000\,007로 나눈 나머지를 출력한다.

예제3

  1. 예제 1

    입력
    3 1
    
    예상 출력
    2
    
  2. 예제 2

    입력
    5 1
    
    예상 출력
    0
    
  3. 예제 3

    입력
    5 2
    
    예상 출력
    3