Good Numbers

Let’s consider a number N is good if and only if the occurrence of each digit is multiple of 3 in the octonal representation of N.
You are good at math, so we want to ask you to calculate how many good numbers with K digits in octonal representation, which are multiple of P. This number may be huge, so you are only to print it modulo 10^9 + 9.
Note that good numbers should be positive and should not have any leading zeroes.
For example, suppose K = 3 and P = 2, good numbers are 222(8), 444(8) and 666(8). 111(8) is not good because it is not the multiple of 2. 102(8) is not good because 1 occurs once, not multiple of 3.

There are multiple (at most 100) test cases. Please process until EOF (end of file).
Each test case contains 2 integers K (1 <= K <= 10^18, K is divisible by 3), P (<8).
At most 15 test cases are big. (K > 1000).

For each test case, print a single integer denoting the answer in one line.

3 1
3 2

7
3

2019 Multi-University Training Contest 4