Home Web Board ProblemSet Standing Status Statistics
long long输出请使用 %lld服务器的python版本为3.4
Problem E: 二队-上海-泡泡堂

Problem E: 二队-上海-泡泡堂

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 15  Solved: 8
[Submit][Status][Web Board]

Description

Pikapikachu很喜欢玩泡泡堂。
已知泡泡堂的地图为N*M的二维方格图,格子上面可以有泡泡,泡泡会爆炸。在某个格子上的泡泡爆炸后,不仅该格子,与该格子相同行或相同列的其他格子,也会受到爆炸的影响。
在所有泡泡没爆炸前,每个格子存在两种状态:有泡泡和没有泡泡。N*M个格子,共有2^(N*M)种泡泡分布方式。
设A(x)表示,当所有泡泡爆炸后,没有受爆炸影响的格子数量为x时,泡泡分布方式的种数。
求 Sum( (A(x) *(x+1) )%(1e9+7),0≤x≤N*M

Input

第一行只包含一个整数T(1≤T≤20),表示有T组数据。
对于每组数据,其包含两个整数N和M(1≤N,M≤200)。

Output

对于每组数据,输出一行结果。
输出格式为“Case #x: y”,x表示数据组数(从1开始),y表示答案。

Sample Input

3
1 1
2 2
3 4

Sample Output

Case#1: 3
Case#2: 24
Case#3: 4864

HINT

[Submit][Status][Web Board]