14884번 - ACG

팀 ACG는 A, C, G로 이루어진 프로그래밍 대회 팀이다. 오늘은 다가오는 ICPC 대회를 준비하려고 한다.

오늘 ACG가 풀 대회는 총 N개의 문제로 이루어져 있다. ACG는 매우 뛰어난 팀이기 때문에, 세상에 존재하는 모든 문제를 풀 수 있다.

연습을 실전처럼 하기 위해 컴퓨터 한 대를 이용해서 연습을 하려고 한다. ACG는 모든 문제를 풀 수 있는 팀이고, 각각의 문제는 A, C, G 세명 모두 풀 수 있다.

문제의 순서는 난이도와 상관이 없는 경우가 많기 때문에, 대부분의 다른 팀은 문제를 순서대로 풀지 않는 경우가 많다. 어차피 모든 문제를 풀 수 있는 ACG는 문제를 항상 주어진 순서대로 해결한다.

이제, 각각의 문제를 누가 풀지 결정해야 한다. 한 문제를 동시에 두 명이 푸는 경우는 없으며, 항상 한 명이 담당해서 해결해야 한다. 아래 조건을 만족하면서 문제를 풀 사람을 결정하는 방법의 수를 구하는 프로그램을 작성하시오.

• A는 정수 k를 매우 좋아한다. 따라서, A가 푼 문제의 수는 k의 배수가 되어야 한다.
• C는 휴식을 좋아하는 친구이기 때문에, 연속해서 두 문제 이상을 풀 수 없다.
• G는 문제를 푸는 것을 좋아하는 친구가 아니다. 따라서, 한 문제 이상만 풀면 된다.

첫째 줄에 테스트 케이스의 개수 T (1 ≤ T ≤ 50)가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있으며, N과 k가 공백으로 구분되어져 있다. (1 ≤ N ≤ 10¹⁸, 0 ≤ k ≤ 10)

문제를 풀 사람을 결정하는 방법의 수를 10000007로 나눈 나머지를 출력한다.