{"problem":{"name":"[PA 2024] Żarówki","description":{"content":"**题目译自 [PA 2024](https://sio2.mimuw.edu.pl/c/pa-2024-1/dashboard/) Runda 5 [Żarówki](https://sio2.mimuw.edu.pl/c/pa-2024-1/p/zar/)，感谢 Macaronlin 提供翻译** 有 $n$ 个灯泡，每个灯泡有两种状态：开和关，初始状态是给定的。有 $m$ 个开关，每个开关","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":3000,"memory_limit":1048576},"difficulty":{"LuoguStyle":"P6"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP10367"},"statements":[{"statement_type":"Markdown","content":"**题目译自 [PA 2024](https://sio2.mimuw.edu.pl/c/pa-2024-1/dashboard/) Runda 5 [Żarówki](https://sio2.mimuw.edu.pl/c/pa-2024-1/p/zar/)，感谢 Macaronlin 提供翻译**\n\n有 $n$ 个灯泡，每个灯泡有两种状态：开和关，初始状态是给定的。有 $m$ 个开关，每个开关控制两个灯泡，按下开关可以使这两个灯泡变为与目前状态相反的状态，只有在两个灯泡有相同状态时才起作用，否则不起作用。\n\n你可以随意安排开关的使用顺序和使用次数，问利用这些开关可以实现多少种配置方案。灯泡在一种配置中打开而在另一种配置中关闭，则两种配置被视为不同。\n\n## Input\n\n第一行两个整数 $n$ 和 $m\\ (1\\le n\\le 200\\,000,0\\le m\\le 400\\,000)$，表示灯泡和开关的个数。\n\n第二行 $n$ 个整数 $c_i\\ (c_i\\in \\{0,1\\})$，如果 $c_i=1$，则初始时第 $i$ 个灯泡是打开的，如果 $c_i=0$，则初始时第 $i$ 个灯泡是关闭的。\n\n接下来 $m$ 行，每行两个整数 $a_i,b_i\\ (1\\le a_i,b_i\\le n,a_i\\neq b_i)$，描述一个开关。\n\n保证开关会影响不同的无序灯泡对。形式化地，$\\forall i,j \\in \\{1,2,\\ldots,m\\},i\\neq j$，都有 $(a_i,b_i)\\neq (a_j,b_j)$ 且 $(a_i,b_i)\\neq (b_j,a_j)$。\n\n## Output\n\n输出一行一个整数，表示利用这些开关可以实现多少种配置方案。输出对 $10^9+7$ 取模。\n\n[samples]\n\n## Background\n\nPA 2024 5C2\n\n## Note\n\n所有可以实现的配置方案为：`10110`，`00010`，`00111` 和 `10011`。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP10367","tags":["数学","图论","2024","图论建模","二分图","组合数学","PA（波兰）"],"sample_group":[["5 4\n1 0 1 1 0\n1 3\n5 3\n4 2\n1 5\n","4"]],"created_at":"2026-03-03 11:09:25"}}