ACG

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

오늘 ACG가 풀 대회는 문제 $N$개로 이루어져 있다. ACG는 아주 뛰어난 팀이라서 세상에 있는 문제를 모두 풀 수 있다.

연습을 실전처럼 하려고 컴퓨터 한 대만 쓴다. 각각의 문제는 A, C, G 세 사람 모두 풀 수 있다.

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

이제 각각의 문제를 누가 풀지 정해야 한다. 한 문제를 두 사람이 같이 푸는 경우는 없고, 언제나 한 사람이 맡아서 해결한다. 다음 조건을 모두 만족하도록 담당자를 정하는 방법의 수를 구하는 프로그램을 작성하시오.

• A는 정수 $k$를 매우 좋아한다. 따라서 A가 푼 문제의 수는 $k$의 배수여야 한다.
• C는 휴식을 좋아하는 사람이라서 연속해서 두 문제 이상을 풀 수 없다.
• G는 문제를 푸는 것을 좋아하는 사람이 아니다. 따라서 한 문제 이상만 풀면 된다.

$k = 0$이면 $0$의 배수는 $0$뿐이므로, A는 한 문제도 풀지 않는다.

첫째 줄에 테스트 케이스의 개수 $T$ ($1 \le T \le 50$)가 주어진다. 각 테스트 케이스는 한 줄로 이루어지며, $N$과 $k$가 공백을 사이에 두고 주어진다. ($1 \le N \le 10^{18}$, $0 \le k \le 10$)

각 테스트 케이스마다 담당자를 정하는 방법의 수를 $10000007$로 나눈 나머지를 한 줄에 하나씩 출력한다.