给定长度为 的整数序列 （下标为 ）和正整数 ，其中 。
定义 。
你需要求出满足以下条件的序列 （下标为 ）数量：
答案对 取模。
第一行两个正整数
第二行 个正整数，描述序列
共一行一个整数，表示 的数量对 取模后的值
样例输入 1
5 2 1 1 2 1 3
样例输出 1
14
样例输入 2
5 5 1 2 3 4 5
样例输出 2
16
样例输入 3
6 2 1 1 4 5 1 4
样例输出 3
24
对于 的数据，。
对于另外 的数据，。
