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.
Input
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).
Output
For each test case, print a single integer denoting the answer in one line.