输入描述:

由于  可能很大，我们采取如下方式读入。

第一行两个数  和常数 ，其中  表示  的值域。

接下来一行  个数，其中第  个数   表示  的在序列出现次数，可以发现在序列中出现的具体位置并不影响答案。

保证 。

输出描述:

一行  个整数，第  个数表示  时的答案，对  取模。