{"problem":{"name":"[ICPC 2024 Xi'an I] Yet Another Maximum Matching Counting Problem","description":{"content":"There is a two-dimensional plane.                You have a set of points $\\{(x_i,y_i)\\}$ that satisfies $1\\le x_i\\le n, 1\\le y_i\\le m$ (Both $x_i$ and $y_i$ are integers), and there are no two points","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":3000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P7"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP10563"},"statements":[{"statement_type":"Markdown","content":"There is a two-dimensional plane.\n    \n    \n    \nYou have a set of points $\\{(x_i,y_i)\\}$ that satisfies $1\\le x_i\\le n, 1\\le y_i\\le m$ (Both $x_i$ and $y_i$ are integers), and there are no two points with the same coordinates.\n    \n    \n    \nIf two points have the same horizontal or vertical coordinates, we will connect an edge between these two points. This forms a graph.\n    \n    \n    \nYou need to find the sum of the maximum number of matches in the graphs formed by all possible $2^{nm}-1$ non empty sets, and output the result modulo $998244353$.\n    \n    \n    \nHere, the maximum number of matches in a graph is defined as: selecting the most edges so that there are no common vertices between any two edges.\n\n## Input\n\nThere are multiple testcases in this problem.\n    \n    \n    \nThe first line contains an integer $T(1\\le T\\le 100)$, which represents the number of testcases.\n    \n    \n    \nEach of the testcases contains two integers $n,m(1\\leq n,m\\leq 500)$.\n\n## Output\n\n \nFor each of the testcases, print an integer representing the result modulo $998244353$.\n    \n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"LGP10563","tags":["2024","O2优化","ICPC","西安"],"sample_group":[["10\n1 1\n1 2\n2 2\n4 4\n3 3\n5 5\n1 8\n20 20\n100 100\n500 500","0\n1\n10\n241456\n964\n200419152\n448\n985051144\n370696900\n357517517"]],"created_at":"2026-03-03 11:09:25"}}