胖头鱼对于当今OI题目的部分分设置极其不满意，许多题目的部分分都只是简单的缩小范围或者给几个特殊的性质。但是胖头鱼只会写有特殊性质的数据的暴力，于是他爆零了。他很生气，认为智障选手也应该拥有得分。于是他在他出的题里面实现了他的信仰。
胖头鱼的题目中，每个测试点有 $26$ 个参数，分别命名为小写字母a到z，题目满分为 $100$ 分。部分分的分布非常有规律，具体如下：
a
z
一个测试点可以用一个有序 $26$ 元组唯一表示，其中的元素为 $[0,99]$ 中的整数。任意合法的二十六元组存在且仅存在一个测试点与它唯一对应。每个测试点的分数是一样的，也就是说，总共有 $100^{26}$ 个测试点，每个测试点分值为 $100^{-25}$。
一份程序能通过的测试点可以用一个只包含字母，数字，小于号，小括号，且运算，或运算的合法表达式表示。当表达式的值为真时，表示可以通过这个测试点。为了形式统一，所有数字均为两位数，如04,11等。其中，符号&表示且，符号|表示或，且的优先级比或高，括号能改变运算顺序。
04
11
&
|
给出表达式（保证合法），请你回答这份程序的得分。
合法的表达式的定义如下：
表达式字母<两位数字合法。其中字母是a到z的小写字母，两位数字是两个0到9的字符的拼接，两个数字不会同时为 $0$。
字母<两位数字
如果表达式A、B都合法，那么A&B与A|B均合法。
A
B
A&B
A|B
如果表达式A合法，则(A)也合法。
(A)
第一行给出一个整数 $m$ 表示有 $m$ 个询问。
接下来行，每行一个字符串表示一个程序能通过的数据范围，保证字符串只由小写字母,<,&,|,(,)及数字组成，并且变量只有一个字母，保证表达式合法。
<
(
)
$1 \le m, |S| \le 80$，其中 $|S|$ 是询问串的长度。
注意，<后的数字是两位数，不会出现a<3、c<9这样的情况。
a<3
c<9
输出 $m$ 行。
对于每个询问，假设该程序的得分为 $\frac{a}{b}$，其中 $a$ 和 $b$ 互质 ，那么请输出 $a \times b^{-1}$ 对 $10^9+9$ 取模的值。($b^{-1}$ 是 $b$ 在模 $10^9+9$ 下的乘法逆元，可以证明在本题的数据范围下，乘法逆元存在，且输出的答案唯一。)
6 b<03&c<07 b<15|a<02 a<50&c<20&d<50|a<30&b<20 (a<50|b<20)&(a<30|d<60) a<30|(a<04|b<20)&(d<60&c<20) a<08|b<20|c<04|d<10
310000003 700000023 400000014 48 480000036 65600037
第一组询问只跟参数b,c有关，有3%的数据满足b<3，其中有7%的数据满足c<7所以符合条件的数据占比为0.03*0.07=0.0021，得分为0.21
第二组询问只跟参数a,b有关，有15%的数据满足b<15，有2%的数据满足a<2，其中有0.15*0.02=0.003的数据同时满足这两个限制。由容斥原理得，符合条件的数据比例为0.15+0.02-0.003=0.167，得分为16.7。
第三组询问，&的优先级更高，考虑|两边的式子，左边有三个参数，同时满足的数据占比为0.5*0.2*0.5=0.05右边是0.3*0.2=0.06，同时满足左右两边的式子（a<30&b<20&c<20&d<50）的数据占比为0.3*0.2*0.2*0.5=0.006所以满足该式子的数据占比为0.05+0.06-0.006=0.104,得分为10.4
Comet OJ