小红叒战小紫
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
64bit IO Format: %lld

题目描述

小红这天又和小紫发起了一场对战。对战的规则如下:
两人各有一些怪兽卡。每回合两人随机的从自己当前存活的怪兽卡中抽取一张发起决斗,战斗力低的怪兽卡死亡。如果两张怪兽卡战斗力相同,则无事发生。
游戏会进行到“如果抽卡,则 100% 的概率无事发生”或者“有一方卡牌被用完”时结束。请你计算小红和小紫游戏进行回合数的期望。

输入描述:

第一行输入两个正整数n, m,分别代表小红和小紫的怪兽卡数量。
第二行输入n个正整数a_i,代表小红的每张怪兽卡战斗力。
第三行输入m个正整数b_i,代表小紫的每张怪兽卡战斗力。
1\leq n,m \leq 50
1\leq a_i,b_i \leq 2

输出描述:

一个整数,代表最终回合数期望对10^9+7取模的值。可以证明,最终的答案一定是个有理数,你只需要输出其对10^9+7取模的结果。
分数取模的定义:假设答案是x/y,那么其对p取模的答案是找到一个整数a满足a∈[0,p-1]a*yp取模等于x
示例1

输入

复制
1 1
1
1

输出

复制
0

说明

显然第一回合都不需要进行,因为一定会无事发生。
示例2

输入

复制
2 3
2 2
1 1 1

输出

复制
3

说明

一定会进行 3 回合,直到小紫的怪兽全部死亡。
示例3

输入

复制
2 1
1 2
2

输出

复制
2

说明

有 1/2 的概率会进行 1 回合,1/4 的概率会进行 2 回合,1/8 的概率会进行 3 回合……
最终答案是 1/2*1+1/4*2+1/8*3+……
该无穷级数收敛于 2。