# 编辑城镇与模拟币3 参考时限：0.5秒；内存限制：64 MiB. 目标平台按正式文件最慢中位数的两倍、向上取整到0.5秒校准，见[评测环境](../../../docs/评测环境与性能.md)。 ## 背景故事 《模拟人生》中的“编辑城镇”允许玩家不投入自己的模拟币就改变城镇的样貌，当然，装修自己家仍然需要花钱。除了建筑和内设，这个模式还可以编辑家庭成员。成员离开时，会带走原家庭按人数等分的一份模拟币。 发现这一机制后，小A又开始研究家庭的财富。这一次，城镇只保留两个家庭位置。居民可以在两个位置之间搬家，空家庭的位置也会保留。小A希望让最初属于1号家庭的成员最终重新组成一个家庭，并使他们拥有的模拟币尽可能多。 小A准备了多份互不相关的城镇存档，请分别计算答案。 ## 形式化问题描述 每份存档始终只有两个家庭位置，记为A、B。初始A位置的家庭有 $p_1$ 人、$m_1$ 单位模拟币；B位置的家庭有 $p_2$ 人、$m_2$ 单位模拟币。初始属于A的所有居民称为目标成员，他们的身份始终不变。目标成员至少有一人，B可以为空。 一次编辑选择一名居民，将其从当前家庭搬到另一个位置的家庭。若搬出前其家庭有 $p$ 人、$m$ 单位模拟币，该居民带走 $m/p$ ；原家庭减少一人和 $m/p$ 单位模拟币，另一个家庭增加一人和同样多的模拟币。加入后的模拟币由新家庭全体成员共同拥有，之后搬出的居民按新的人均财富带走模拟币。 允许搬入空家庭。家庭变空后，其位置仍然保留，模拟币为0；不能建立第三个家庭位置。编辑期间及最终的家庭人数没有上限。模拟币按精确有理数计算，不能凭空增减。 可以进行任意有限次编辑，也可以不编辑。最终，全部目标成员必须共同组成一个家庭，且该家庭不含其他居民。这个家庭可以位于A，也可以位于B。求其模拟币总数的最大值 $W$ . 应先在精确有理数意义下最大化，再输出 $W$ 对 $P=1000000007$ 取模的结果。若约分后 $W=u/v$ ，其模值为 $u\cdot v^{-1}\bmod P$ ，输出 $[0,P-1]$ 内的代表元。在给定范围内，最大值可以用有限次编辑达到，且分母与 $P$ 互素。 ![目标成员在两个固定位置间搬家，最终在B组成财富为98/9的家庭](assets/example.svg) 图中 $T_1,T_2$ 是目标成员，$O_1,O_2$ 是其他居民，$M$ 表示该家庭的模拟币总数。每一步只搬一人，始终只有A、B两个位置。 ## 输入格式 第一行一个整数 $T$ ，表示存档数量。 每份存档占两行。第一行为 $p_1,m_1$ ，第二行为 $p_2,m_2$ . ## 输出格式 对每份存档输出一行一个整数，表示最大模拟币总数的模值。 ## 样例 1 ### 输入 ```text 1 2 2 2 18 ``` ### 输出 ```text 888888906 ``` 图中四次搬家依次为 $T_1$ 从A到B、$O_1$ 从B到A、$T_2$ 从A到B、$O_2$ 从B到A。最终B恰好包含两名目标成员，财富为 $98/9$ ，其模值为888888906。这是最优值。 ## 样例 2 ### 输入 ```text 1 3 12 2 4 ``` ### 输出 ```text 12 ``` 目标家庭初始人均财富较高，不编辑即可达到最优值12。 ## 样例 3 ### 输入 ```text 1 2 2 1 9 ``` ### 输出 ```text 8 ``` 目标成员可以暂时分开，最终在B组成财富为8的家庭。 ## 样例 4 ### 输入 ```text 1 1 0 1 1 ``` ### 输出 ```text 500000004 ``` 先合并两人，再让目标成员搬到空位置，目标财富为 $1/2$ . ## 样例 5 ### 输入 ```text 1 7 25 0 0 ``` ### 输出 ```text 25 ``` 另一个家庭为空，全部模拟币都属于目标成员，答案为25。 ## 样例 6 ### 输入 ```text 3 2 6 3 9 3 1 2 1 1000000 1000000000 1 1000000000 ``` ### 输出 ```text 6 930041160 286420940 ``` 三份存档独立处理。第一份存档中两户人均财富相等；第二份的最大财富为 $298/243$ . ## 数据范围与保证 $1\le T\le100000$ ，$1\le p_1\le1000000$ ，$0\le p_2\le1000000$ ，$0\le m_1,m_2\le10^9$ .若 $p_2=0$ ，则 $m_2=0$ . 本题由 Codex（GPT-6）重新设计：家庭位置固定为两个，允许空家庭及多名目标成员，只求目标成员重新组成家庭后的最大财富，最终可以使用任一位置；输入包含多份独立存档。 | 分值比例 | 额外条件 | | --- | --- | | 100% | 无额外条件 | 共10个正式文件，每个10%。[数据生成与检验](tests/README.md)。另见[编辑城镇与模拟币2](../town-editing-simoleons-2/statement.zh.md)。