팀 연습 더
시간 제한1초메모리 제한512 MB
N개의 문제를 세 사람에게 배정하되 A가 푸는 개수는 K의 배수이고 B는 연속으로 풀 수 없으며 C는 최소 한 문제를 풀어야 할 때, 가능한 배정의 수를 10^9+7로 나눈 나머지를 구한다.
문제
A, B, C 세 사람이 다가오는 ICPC 대회를 준비하려고 팀 연습을 한다. ICPC는 팀 대회이므로 누가 어떤 문제를 푸는지 정하는 일도 중요하다. 그래서 오늘 연습에서는 세 사람 모두가 풀 수 있는 문제 N개를 푼다. 문제에는 1번부터 N번까지 번호가 붙어 있다.
세 사람이 문제 N개를 푸는 방식은 다음과 같다.
- 문제는 1번부터 번호가 커지는 순서대로 해결해야 한다.
- 각 문제를 푸는 사람은 세 사람 중 한 명이다.
- A가 해결한 문제의 수는 K의 배수여야 한다.
- B는 문제를 연속해서 풀 수 없다.
- C는 문제를 한 개 이상 해결해야 한다.
N과 K가 주어졌을 때, 문제를 푸는 사람을 정하는 방법의 수를 구하자.
입력
첫째 줄에 N (1 ≤ N ≤ 10^18), K (0 ≤ K ≤ 10)가 주어진다.
출력
첫째 줄에 문제 N개를 모두 푸는 사람을 정하는 방법의 수를 1,000,000,007로 나눈 나머지를 출력한다.