Description

给你一个n*m的格子,可以用若干个环把这些格子的中心串连起来.上下左右可以互相连接. 要求每个格子属于且仅属于一个环,所有环不能交叉.

2*2的只有一种连接方案:

Input

多组数据(不超过60),每组数据两个整数n,m(1<=n<=7, 1<=m<=10^9).

Output

首先输出case数,然后输出所有可行的方案数,结果取模1,000,000,007.

Sample

Input

2 2
2 3
2 4

Output

Case 1: 1
Case 2: 1
Case 3: 2

Source: dd