经典 DP

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

题目描述

$\hspace{15pt}$ 给定初始值 $c$ 和一个由 $n$ 个正整数组成的数组 $\{a_1, a_2, \dots, a_n\}$ ，定义一次操作如下：
${\hspace{20pt}}_\texttt{1.}\,$ 选择数组 $a$ 中的若干个元素（至少一个），记元素之和为 $s$ ；
${\hspace{20pt}}_\texttt{2.}\,$ 将 $c$ 更新为 $c\times s$ 。
$\hspace{15pt}$ 求解有多少种不同的操作方案，使得恰好经过 $t$ 次操作后 $c\bmod m=k$ 。由于答案可能很大，请将答案对 $(10^9+7)$ 取模后输出。

$\hspace{15pt}$ 记第 $i$ 次选取元素的下标构成的集合为 $\Bbb S_i$ ，两个方案被视为不同的，当且仅当存在 $i$ 使得两个方案第 $i$ 次选取元素的下标构成的集合不同。

输入描述:

第一行输入一个正整数 ，代表数组元素个数。
第二行输入  个正整数 ，代表数组中的元素。
第三行输入四个整数 ，代表初始值、模数、余数、恰好操作次数。

输出描述:

输出一个整数，表示不同的操作方案数量。由于答案可能很大，请将答案对  取模后输出。

示例1

输入

复制

1
1
1 2 1 1

输出

复制

示例2

输入

复制

2
1 2
1 100 2 101

输出

复制

133357702

示例3

输入

复制

2
1 2
1 100 2 3

输出

复制

示例4

输入

复制

3
1 2 3
1 1 0 4

输出

复制