{"problem":{"name":"[EGOI 2022] Lego Wall / 乐高墙","description":{"content":"有两种乐高积木，大小分别为 $1\\times 1\\times 1$ 和 $2\\times 1\\times 1$（宽、高、长）。两种积木你都有无限个，每种积木的所有积木块没有任何区别。 ![](https://cdn.luogu.com.cn/upload/image_hosting/1y2rwj59.png) 一个积木块总是以正确的方向使用。四周的面是用同一种材料制成的，除了大小以外没有区别。","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":3000,"memory_limit":262144},"difficulty":{"LuoguStyle":"P6"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9318"},"statements":[{"statement_type":"Markdown","content":"有两种乐高积木，大小分别为 $1\\times 1\\times 1$ 和 $2\\times 1\\times 1$（宽、高、长）。两种积木你都有无限个，每种积木的所有积木块没有任何区别。\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/1y2rwj59.png)\n\n一个积木块总是以正确的方向使用。四周的面是用同一种材料制成的，除了大小以外没有区别。\n\n我们称两个积木块**锁死**，当且仅当一个块在另一个块的正上方。称两个积木块 $b_0$ 和 $b_k$ **连通**，当且仅当存在一个积木块序列 $b_0,b_1,\\ldots,b_k$，使得任意相邻积木块 $b_{i-1}$ 和 $b_i$ 锁死。我们称一组积木块**连通**，当且仅当组内的每一对积木块都连通。\n\n你希望搭建一个大小为 $w\\times h\\times 1$ 的积木墙，使得这面墙**没有洞**且**连通**。以下是 $4\\times 3\\times 1$ 的积木墙的例子：\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/ehrcz8d7.png)\n\n另一方面，下面的 $4\\times 3\\times 1$ 的积木墙不连通，因此不被需要：\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/twsqgt8x.png)\n\n有多少种搭建**没有洞**且**连通**的积木墙的方案呢？答案可能很大，请输出它对 $10^9+7$ 取模的结果。\n\n注意一个积木墙的镜像版本（旋转 $180^\\circ$）和原来的版本被认为不同，除非他们看起来一模一样。\n\n## Input\n\n一行，两个整数 $w,h$——积木墙的宽度和高度。\n\n## Output\n\n一行，一个整数，表示方案数对 $10^9+7$ 取模的结果。\n\n[samples]\n\n## Background\n\nDay 1 Problem B.\n\n题面译自 [EGOI2022 legowall](https://stats.egoi.org/media/task_description/2022_legowall_en.pdf)。\n\n[![CC BY-SA 3.0](https://licensebuttons.net/l/by-sa/3.0/80x15.png)](https://creativecommons.org/licenses/by-sa/3.0/)\n\n## Note\n\n**样例 $1$ 解释**\n\n三种方案如图所示：\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/yi7xhw9f.png)\n\n---\n\n**数据范围**\n\n对于全部数据，$1\\le w\\le 2.5\\times 10^5$，$2\\le h\\le 2.5\\times 10^5$，$w\\times h\\le 5\\times 10^5$。\n\n- 子任务一（$14$ 分）：$w=2$。\n- 子任务二（$12$ 分）：$h=2$。\n- 子任务三（$18$ 分）：$w,h\\le 100$。\n- 子任务四（$30$ 分）：$w\\le 700$。\n- 子任务五（$20$ 分）：$h\\le 700$。\n- 子任务六（$6$ 分）：无特殊限制。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9318","tags":["2022","O2优化","EGOI（欧洲/女生）"],"sample_group":[["2 2","3"],["3 3","12"],["5 7","1436232"]],"created_at":"2026-03-03 11:09:25"}}