B. Misaka Network 与任务

测试完毕之后，研究者们现在要用 Misaka Network 进行任务。当前能处理任务的个体一共有 个，以及 个处理任务的方案（可能相同），第 个方案给出一个 位二进制数 ，表示选用 这个集合的个体进行任务。现在一共要进行 次任务，每次任务可以选取任意一个方案，然后由这个方案的集合 的所有个体合作完成，要求至少有一个个体参加了所有的 次任务。

求出不同的选择方式数对 取模的结果，两种选择方式不同，当且仅当它们在某一次任务选择的方案的编号不同。

第一行三个整数 、、。

接下来一行 个整数 ，以十进制的方式给出。

一行一个整数，表示方案数对 取模的结果。

样例输入 1

2 3 4
1 2 3

样例输出 1

31

样例输入 2

4 8 8
7 2 8 2 4 3 15 4 

样例输出 2

456160

对于所有数据 。