给定初始值 和一个由 个正整数组成的数组 ，定义一次操作如下： 选择数组 中的若干个元素（至少一个），记元素之和为 ； 将 更新为 。 求解有多少种不同的操作方案，使得恰好经过 次操作后 。由于答案可能很大，请将答案对 取模后输出。 记第 次选取元素的下标构成的集合为 ，两个方案被视为不同的，当且仅当存在 使得两个方案第 次选取元素的下标构成的集合不同。

输入描述:

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

输出描述:

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