你继续向前走，遇到了一个身着黑袍的老人，那边的门前放着一个巨大的沙盘，老人用手中的树枝在沙盘前画着奇怪的符号。
老人告诉你，他从年轻开始便梦想一个问题，直到他垂垂老矣，似乎也只揭露了答案的一角。
或许我该将它们交给你们了，老人说。
别太担心，我不想太为难你，至少我已经把必要的工具给你准备好了。
对于正整数 ，考虑下述长为 的序列 ：
对于每个 ，序列 中出现了恰好 个 。
对于 满足 ，那么对任意 ，有 。
我们称满足上述要求的序列是一个 阶排列。
现在输入一个 阶排列 。又给定 和 ，请你计算有多少 阶排列包含子序列 ，并且满足：
你只需计算出这样的序列总数对 取模的结果。
第一行输入四个整数 ，，，。
第二行输入 个正整数，保证构成一个 阶排列。
输出一个整数，表示满足要求的序列的数量。
1 4 2 2 2 1
7
2 4 2 2 1 2 2 1
19
子任务 （ 分）：保证 。
子任务 （ 分）：保证 ，。
子任务 （ 分）：无特殊限制。
对于所有数据，保证 ，，，。
为了方便选手处理形式幂级数的运算，我们提供了一个模板。选手可以根据自己的需要参考与使用该模板，也可以不使用该模板。
