本题的评测时间较长，若发现有恶意利用此题堵塞评测队列的，我们会采取包括但不限于禁赛等措施
视传奇旅人伊雷娜小姐为偶像的碳钾钨因憧憬成为魔女而报考了重庆魔法大学的法阵工程专业！但是一入学碳钾钨就遇到了难题，于是他打算向你求助。
结构化法术设计的老师给碳钾钨布置了一个任务：试计算有多少种不同的长度为的咒语序列合法。一个长度为的魔法咒语序列可以用一个长度为的数组表示。为判定要给序列是否合法，老师给定了个互不相同的魔法关键值和两个整数，第个魔法关键值用表示。对于一个魔法序列，若同时满足以下两个条件则合法：
因为答案可能很大，老师只要求输出合法的咒语序列数量，且答案对取模。
求求你帮碳钾钨解决这个问题，等碳钾钨成为魔女后，会把这段往事写到日记中的。
形式化的说：现给定三个整数和长度为的互不相同的数组
求有多少个不同的长度为n的非负整数数组满足以下两个条件
求满足条件的数组的个数，答案对取模
第一行三个整数。
第二行个整数，其中第个整数表示
一个整数，表示合法的数组的个数，答案对取模
输入
3 3 2 1 2 3
输出
5
其中
样例中合法的长度为3的魔法序列有以下五种：
2 1 1 3 1 1 3 1 2 3 2 1 3 2 2
