打到济南府 活捉王耀武
Background
本题属于睿爸信奥课程思政系列题目。 学信奥顺便把历史也学了。
Description
1948年7月，华东野战军主力豫东战役和山东兵团大反攻作战胜利后。7月14日，毛泽东指示华野，下一个目标是解放济南。
遵照毛泽东的指示，8月20日，粟裕等华野指挥员与山东兵团指挥部在曲阜会合，研究济南战役的作战方针。这是1947年7月分兵以来，华野两大集团指挥员的重新会合。
此时，国民党统帅部也在南京召开军事检讨会。蒋介石总结前段失败的教训，决定在中原组建邱清泉、黄百韬、李弥、孙元良四个机动兵团。在济南、青岛、开封等地设绥靖区，最大的是济南第二绥靖区，由王耀武指挥3个整编师部、9个正规旅、5个保安旅约11万兵力驻守。
济南是国民党山东省会，人口70万。王耀武获悉粟裕主力已经返回鲁西南，他认为十有八九是冲着济南来的。为此，他一面请求蒋介石将83师空运济南；一面命令增强工事。
8月27日，蒋介石下令将83师空运济南。他的计划是如果共军进攻济南，立即调动邱清泉、黄百韬、李弥三个兵团北上增援，以南北夹击消灭华东野战军。
王耀武在济南利用外城墙和内城墙构筑了三道防线，修筑子母堡和众多火力点，他认为外围能坚守半个月，城区至少能坚持一个月。
为确保战役的胜利，粟裕请求军委将苏北兵团主力调来参加打援战斗，得到军委批准。这样，在攻济打援战场上敌我兵力对比，我军取得了优势。
山东兵团司令员许世友因病没有参加曲阜会议。毛泽东点将由许世友担任攻城主要指挥员。粟裕将部队分为攻坚和打援两大集团。攻坚集团由许世友、谭震林指挥三、九、十纵等6个纵队，总兵力14万人；打援集团由粟裕统一指挥一、二、四纵等7个纵队，总兵力18万人。他们提出响亮的口号：打到济南府，活捉王耀武！华东局调集各根据地的50多万民工，为济南战役提供了强大的后勤保障。
从9月9日起，担任攻城任务的部队分别从不同的方向向济南郊区隐蔽开进。
11日，许世友来到济南前线指挥所。当日，毛泽东来电强调：整个攻城指挥，由你们担负。全军指挥，由粟裕担负。毛泽东一锤定音，对济南战役的胜利起到决定性的作用。
王耀武不断收到20万共军向济南集结的报告，他认为要想守住济南，必须增加兵力。但徐州方面对增兵济南一直很不积极。到9月12日，仅将83师的19旅运到济南。
9月15日，王耀武到南京当面向蒋介石告急。蒋介石答应调74师增援济南，同时指示王耀武固守济南，待援军一到南北夹击打败共军。就在王耀武匆匆飞回济南的当晚，济南外围战斗打响，拉开了济南战役的序幕。
1948年9月16日夜，我攻城部队分东西两个集团，从东西两个方向发起攻击。西线很快占领了金牛山、琵琶山、孟庄等一批外围据点，逼近济南机场。
17日晨，东线我军攻占战略要点茂岭山和砚池山。令王耀武大为震惊。
我军的迅速推进，使防守济南西区簸箕山、辛店的第96军吴化文部，完全暴露在我军的面前。在强大军事压力下，吴化文于19日晚率部2万多人战场起义。
王耀武感到大势已去，紧急向蒋介石请求突围，遭到蒋介石的拒绝。
吴化文部的起义，使我军迅速突入商埠，并于20日占领济南机场。21日晨，我军占领国民党山东省党部。22日晚，我军完全占领商埠。
我军置外围据点历城和千佛山之敌于不顾，除少数部队包围监视外，主力绕过这两处据点向外城攻击。
此时，王耀武还有四个旅兵力集结于外城和内城。为不给敌军调整部署和加强工事的时间，许世友决心连续进攻。
22日黄昏，东、西集团同时向济南外城发起攻击，从多个方向攻入外城，并于当晚将外城完全控制。
这时，王耀武只剩下内城最后一道防线。蒋介石焦急万分，一面严令邱清泉、黄百韬北上，一面命令空军轰炸济南。
济南危在旦夕，说好增援呢？按照国民党军的计划，济南开战五天后，当共军受到重大伤亡，再出动北上解围。但战役刚开始，蒋介石就发觉形势不妙，急令迅速北上增援。
打援集团在粟裕亲自指挥下，在兖州、邹县地区严阵以待。邱清泉深知北上凶多吉少，有意拖延，到济南战役结束，才到达成武、曹县一带，未与我军接触即迅速后撤。假设济南是一个长为n宽为m的矩形，王司令的司令部是一个矩形的院子，四周需要修建矩形围墙。王司令把修建围墙加司令部的活交给了他的亲戚的建筑公司，让他们先计算下方案数，因为王司令相信狡兔三窟，觉得方案数越多越安全。为了简单起见，我们假设围墙和司令部大院的坐标必须是整数。围墙可以利用济南的城墙，但是因为需要架设火力点，司令部和围墙必须距离至少为1。
23日黄昏总攻开始，我军集中炮火向内城猛轰。突击部队经过数小时爆破、攀登城墙，与敌反复争夺激战，终于在24日凌晨突入内城街道，与敌军展开巷战。
9月24日天明，济南城内的国民党军一片混乱。王耀武眼看大势已去，带领少数随从突围逃跑。
24日下午，我军包围了国民党山东省政府。国民党第2绥靖区参谋长罗辛理等走出地下室缴械投降。黄昏时，内城战斗结束。城外历城和千佛山守敌也于25、26日放下武器。济南战役胜利结束。
28日，王耀武在化妆出逃的路上，被我地方民兵抓获。
济南战役，我军全歼国民党军84000余人，其中毙、伤22423人，俘虏王耀武等将级军官23人。策动吴化文部20000多人起义。华东野战军也为此付出了伤亡26991人的代价。
济南战役是人民解放军在解放战争中第一次攻克有敌军重兵防守和坚固设防的大城市。济南战役的胜利，使华北、华东两大解放区完全连成一片。
Format
Input
第一行，一个正整数T()，表示测试数据组数。
对于每组测试数据，每行包含两个正整数n,m()。
Output
对于每个测试数据每行输出一个整数，表示合法的方案数量，答案对取模。
Samples
2
3 3
5 5
1
225
Limitation
1s, 1024KiB for each test case.