Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official. ×

Please help me with this *2700 problem from my teacher

Revision en2, by thanhchauns2, 2021-04-21 10:21:01

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.

Tags *2700, #divide-and-conquer, chess

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English thanhchauns2 2021-04-21 10:21:01 46
en1 English thanhchauns2 2021-04-21 10:18:55 1849 Initial revision (published)