**Magnus is the youngest chess grandmaster ever. He loves chess so much that he decided to decorate his home with chess pieces. To decorate his long corridor, he decided to use the knight pieces. His corridor is covered by beautiful square marble tiles of alternating colors, just like a chess board, with n rows and m columns. He will put images of knights on some (possibly none) of these tiles. Each tile will contain at most one knight.**↵
****↵
**The special thing about his arrangement is that there won’t be any pair of knights can attack each other. Two knights can attack each other if they are placed in two opposite corner cells of a 2 by 3 rectangle. In this diagram, the knight can attack any of the Xs.**↵
↵
↵
****↵
**Given the dimension of the long corridor, your task is to calculate how many ways Magnus can arrange his knights. Two arrangements are considered different if there exists a tile which contains a knight in one arrangement but not in the other arrangement (in other words, rotations and reflections are considered different arrangements).**↵
↵
**_**Input****_↵
↵
Each input will consist of a single test case. Note that your program may be run multiple times on different inputs. Each test case will consist of a single line with two integers n and m (1≤n≤4, 1≤m≤10^9) representing the dimensions of the carpet. There will be a single space between n and m.↵
↵
**_**Output****_↵
↵
Output a single line with a single integer representing the number of possible arrangements, modulo (10^9+9).↵
↵
Sample Input 1↵
↵
1 2↵
↵
Sample Output 1↵
↵
4↵
↵
Sample Input 2 ↵
↵
2 2↵
↵
Sample Output 2↵
↵
16↵
↵
Sample Input 3 ↵
↵
3 2↵
↵
Sample Output 3↵
↵
36↵
↵
He said I need to Divide and Conquer, however I got no idea about that.
**The special thing about his arrangement is that there won’t be any pair of knights can attack each other. Two knights can attack each other if they are placed in two opposite corner cells of a 2 by 3 rectangle. In this diagram, the knight can attack any of the Xs.**↵
↵
↵
**Given the dimension of the long corridor, your task is to calculate how many ways Magnus can arrange his knights. Two arrangements are considered different if there exists a tile which contains a knight in one arrangement but not in the other arrangement (in other words, rotations and reflections are considered different arrangements).**↵
↵
↵
Each input will consist of a single test case. Note that your program may be run multiple times on different inputs. Each test case will consist of a single line with two integers n and m (1≤n≤4, 1≤m≤10^9) representing the dimensions of the carpet. There will be a single space between n and m.↵
↵
↵
Output a single line with a single integer representing the number of possible arrangements, modulo (10^9+9).↵
↵
Sample Input 1↵
↵
1 2↵
↵
Sample Output 1↵
↵
4↵
↵
Sample Input 2 ↵
↵
2 2↵
↵
Sample Output 2↵
↵
16↵
↵
Sample Input 3 ↵
↵
3 2↵
↵
Sample Output 3↵
↵
36↵
↵
He said I need to Divide and Conquer, however I got no idea about that.
