Description
There are so many buildings constructing in our campus! Instead of constructing a complicated structure, a modern building is made up of square modules, and every room is in the same shape and with same size. Following figure show a 3×4 model.
Now we want to set up a conveyor belt to put some stuff onto it. In every floor, there are two special rooms that must be the beginning and terminal of conveyor belt. The start room is at the northern-west corner, and the end room is at the southern-west corner. Because of the reachability and reduce cost, the conveyor belt has to pass through each room once and only once.
It’s important to know whether it is possible to have such configuration, so they ask you to answer it. Moreover, they also want to know how many ways to achieve such configuration. Following is an 3×3 example that has two ways.
Input
There are no more than 5,000 test cases. Every test case contains two integers, n and m, representing a n × m model, where 2 ≤ n ≤ 4, 1 ≤ m ≤ 109.
Output
Output the number of way to achieve such configuration. Since the number maybe very large, you should take modulo by 7,777,777.If there is no such configuration, output “Impossible”.