Let an archer be a chessman that can move one square forward, back, to the left, or to the right. An archer is situated at the square (1, 1) of an N × M chessboard (the upper right square of the board is coded as (N, M)). The archer's goal is to travel through the board and return to the initial position in such a way that each square of the board is visited exactly once (the travel starts with the first move of the archer). It is required to determine the number of different ways to perform such a travel.

Integers N and M separated with a space. 2 ≤ N ≤ 5; 2 ≤ M ≤ 10⁹.

You should output the number of ways to travel through the board calculated modulo 10⁹.