Fly

题号：NC239325
时间限制：C/C++/Rust/Pascal 6秒，其他语言12秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

Groudon wanna fly. Kyogre will tell Groudon how to fly if and only if Groudon solves the following problem.

There are $n$ integers $a_1,a_2,\ldots,a_n$ , one integer $m$ and $k$ integer pairs $(b_1,c_1), (b_2,c_2), \ldots, (b_k,c_k)$ . You need to find the number of non-negative $n$ -tuples $(x_1,x_2,\ldots,x_n)$ which satisfies:

$\begin{cases} \displaystyle \sum_{i=1}^na_ix_i \le m \\ \displaystyle x_{b_i} \operatorname{\&} 2^{c_i} = 0 \text{ for } i =1,2,\ldots,k \end{cases}$

Here, $\operatorname{\&}$ denotes the bitwise operation AND.

Two non-negative $n$ -tuples $(x_1,x_2,\ldots,x_n)$ and $(x'_1,x'_2,\ldots,x'_n)$ are considered different if and only if there exists one integer $i \in [1,n]$ which satisfies $x_i \ne x'_i$ .

Since the answer is too large, Kyogre only wants to know it modulo $998\,244\,353$ .

You, as a programmer of Hoenn, please help Groudon!

输入描述:

The first line contains three integers  ().

The second line contains  integers  ().

For the -th line in the following  lines, there are two integers  ().

All numbers in the input denote the parameter of Kyogre's problem.

输出描述:

Print a single integer, denoting the answer to Kyogre's problem, modulo .

示例1

输入

复制

3 5 1
2 3 3
1 0

输出

复制

示例2

输入

复制

6 10 2
1 1 4 5 1 4
3 1
4 2

输出

复制

备注:

In the first example, there are  non-negative -tuples satisfy the condition in Kyogre's problem: , , , .