如果您想查看本场比赛的  PDF 格式题面可以：点我下载

小苯正在学习 A+B Problem，为此他从家中翻出了恰好八个"七段码数位显示器"（以下简称显示器）。

如下图所示，显示器共有 个灯管，图中已标明编号。点亮其中的一些灯管就可以形成合法的数字， 的对应的点亮结果如下图二，其中红色灯管是被点亮的，灰色则是未被点亮（其余的结果均是不合法的数字）。

图1: 灯管编号                      图2: 数字  对应的状态                                   

遗憾的是，放置时间太久导致所有的显示器都发生了相同的故障，具体来说，在点亮他们的编号为 的灯管时，灯管都是仅有 的概率会被点亮，而还会有 的概率不会被点亮（各根灯管的点亮尝试相互独立；不同显示器之间、同一显示器内不同编号灯管之间的点亮结果均互不影响）。

但小苯的学习还得进行下去，现在他会让小红指定一个整数 ，接着小苯会将其中的四个排成一排，另外四个排成另一排，并对其 根灯管（共 根）均各尝试一次点亮操作。（由于所有显示器参数相同，具体选哪 台放在第一排与第二排均等价，可视为任意固定分配）。

现在请你计算出如下事件的概率（需全部满足）：
最终所有显示器均有灯管被点亮（也就是说显示器的灯管不能全灭）。
最终所有显示器显示的结果均为合法数字。
第一排的显示器前后拼接形成的四位十进制数记作 ，第二排的显示器前后拼接形成的四位十进制数记作 的话，满足：。（两排显示器从左到右依次作为千位、百位、十位、个位进行拼接，可以存在前导 ）。

如果您不了解分数取模，可以查看下方的备注。

输入描述:

每个测试文件均包含多组测试数据。第一行输入一个整数  代表数据组数，每组测试数据描述如下：

第一行输入一个整数 ，表示小红指定的整数。
第二行输入七个整数 ，分别表示显示器中，每一根灯管在尝试点亮时，被点亮的概率百分比（概率为 ）。

输出描述:

对于每一组测试数据，新起一行输出一个整数，表示最终的概率（对  取模，注意： 是一个质数）。
可以证明答案可以表示为一个不可约分数 ，为了避免精度问题，请直接输出整数  作为答案，其中 ， 是满足  的整数。

注意，如果您不了解分数取模，可以查看下方的备注。

3
0
100 100 100 0 100 100 100
0
100 100 100 0 50 100 100
34
24 54 10 12 33 1 99

1
994344961
20591129

对于第一组测试数据，所有的显示器都恰好只能显示出 ，因此显示出  的四个显示器显示  的概率为 ，显示出  的也为 ，因此  一定成立，即概率为 。
对于第二组测试数据，所有的显示器都恰好有  的概率显示出 ，而另  的概率显示非数字的不合法结果，因此四个显示  的显示器显示出  的概率为：，显示  的也同理。因此  的概率为 ，对  取模的值为 。

备注:

分数取模的提示（教程）：
以下文中的  表示取模，也就是大家平时写的  符号。

我们以任意分数： 举例。
直接给出结论：根据费马小定理，在模数  为质数，且  不是  的倍数的情况下有：。

也就是说在  的意义下，。
例如：在  的情况下，，这是因为  是一个质数，且  不是  的倍数。

上式中， 实际上就是我们常说的 "乘法逆元"，即把 " 除以 " 转化为 " 乘上  的逆元"，这样一来结果算下来是正确的，同时我们将分数（也就是小数）域下的运算转为了整数域下的运算，这样一来就避免了小数可能产生的精度问题，同时不影响答案的正确性。
证明需要大量计算，这里不再展开，我们只需要使用结论即可。