花环争夺战
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

今天是愚人节，Askalana宣布：“4月19日将会迎来一年一度的‘小熊之星’程序设计大赛，在本次大赛获胜的大英雄将会获得我亲手制作的花环，佩戴我制作的花环参加接下来各地区的邀请赛将会获得额外的buff加成哦😘”摩卡甜心为了获得Askalana制作的花环，开始了小熊之星的备战计划。（PS：小熊之星是什么，相信看完了介绍你会懂的(｡･ω･｡)ﾉ♡）
        已知小熊之星的官网上可以vp往年的真题，但vp一次真题需要枚金币，每天可以通过在官网上签到次获得枚金币（一天只能签到次）。
        距离小熊之星还有天，已知摩卡甜心目前有枚金币，目前他在小熊之星大赛中能够获胜的概率为\textit{P%}，如果当天摩卡甜心的金币足够，或者当天签完到后金币足够，那么他在当天一定会vp一场往年的小熊之星真题（当天只会vp一场）。
        下面给出一个长度为的只包含和的字符串，表示摩卡甜心的签到情况（表示未签到，表示签到），并给出天内vp小熊之星真题能够提升的获胜几率p_{1}\textit{%},p_{2}\textit{%},…,p_{18}\textit{%}。如果目前摩卡甜心的获胜概率为\textit{P%}，那么在第天时vp一场往年小熊之星真题后获胜概率会变为\mathit{P}\textit{%}\times \left ( 1+p_{i}\textit{%} \right )。请你帮助摩卡甜心预测一下天后摩卡甜心能够在小熊之星大赛中获胜的概率是多少。

输入描述:

每个测试文件均包含多组测试数据，第一行输入一个整数\textit{T}\left ( 1\leqslant \textit{T}\leqslant 10^{4} \right )，表示数据的组数。
第二行为空格分隔的两个整数和，其中表示摩卡甜心目前拥有的金币数量，\textit{P%}为摩卡甜心目前（可以视为第天）在小熊之星大赛中能够获胜的概率。\left ( 0\leqslant k\leqslant 1000;0\leqslant P\leqslant 100 \right )
第三行为一个长度为的只包含和的字符串，表示接下来的天内摩卡甜心的签到情况。
第四行为个由空格分隔的整数，其中p_{i}\textit{%}为第天vp小熊之星真题能够提升的获胜几率。\left ( 0\leqslant p_{i}\leqslant 100 \right )

输出描述:

    可以证明答案为一个不可约的分数，为了避免精度问题，请直接输出整数作为答案，其中，是满足的整数。
    更具体地，您需要找到一个整数\textit{x} ∈ \left [ 0,10^{9}+6 \right ]，满足对取模等于，您可以查看样例解释获得更具体的说明。（注意：最后计算得出的实际概率可以大于）
示例1

输入

复制 
2
69 50
100000000000000000
20 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
399 82
000000000000001110
42 78 73 10 8 54 15 27 63 11 72 25 97 61 89 36 91 64

输出

复制 
200000002
717466538

说明

在第一组测试数据中，摩卡甜心在第天的获胜概率为\textit{50%}=\frac{1}{2}，他只在第天进行了签到，签到后金币为，于是在第天vp了小熊之星的真题，获胜概率变为，因此摩卡甜心的获胜概率即为，我们可以找到，对取模后恰好等于分子，因此就是我们要找的答案。