题目描述

题目背景纯属虚构。

小 L 和小 J 去夹娃娃。街上一共有 $n$ 家娃娃店，第 $i$ 家娃娃店有 $a_i$ 台娃娃机。一台娃娃机里只有一种娃娃，所有娃娃机里的娃娃都互不相同。在开始夹娃娃之前，小 L 和小 J 已经预估了每一台娃娃机的难度，对于第 $i$ 家店里的第 $j$ 台娃娃机，需要花恰好 $b_{ij}$ 元夹到一个娃娃，并且一共只有 $c_{ij}$ 个娃娃。 小 L 和小 J 一共去了 $q$ 次。第 $i$ 次去的时候，一共带了 $m_i$ 块钱。小 J 突然很喜欢某些娃娃店，想要在这些店里各花至少 $k_i$ 块钱。小 L 想知道一共有多少种夹娃娃的方式（不一定要把钱全部花完），对 $p$ 取模，其中 $p$ 为 $998244353$ 或 $10^9+7$。

两种方式不同当且仅当至少一种娃娃在两个方式中被夹到的数量不同。询问之间相互独立，即每次去夹娃娃时数量都会恢复初始状态。

输入格式

第一行三个整数 $n,q,p$ 表示娃娃店数量，询问次数和模数。

接下来 $n$ 行，每行第一个整数 $a_i$，然后 $a_i$ 对整数 $b_{ij}$ 和 $c_{ij}$ 描述每台娃娃机。

接下来 $q$ 行，每行一个 01 串和两个整数 $m_i,k_i$，串的第 $j$ 个字符为 1 表示小 L 突然很喜欢第 $j$ 家娃娃店。

输出格式

一共 $q$ 行，每行一个整数表示答案对 $p$ 取模的结果。

样例输入

4 6 998244353
1 2 1
2 3 4 5 6
2 2 2 1 3
2 9 9 13 14
0101 12 1
1010 4 1
1111 100 10
0000 5 500
0110 10 2
0101 200 40

样例输出

1
3
0
22
40
1950

数据范围

对于所有数据，$1\le n\le 15$，$1\le m_i,k_i,a_i,b_{ij},c_{ij}\le 520$，$1\le q\le 52099$。