题目描述

带加强同学定义了一种“铁”的有根树：对于树中每个非叶节点，若其有 ( x ) 个孩子，则 ( x \in D )（( D ) 是给定的正整数集合）。

请回答 ( T ) 次询问，每次给定 ( n )，求有 ( n ) 个叶子的“铁”树的数量，答案对 ( M ) 取模。

输入格式

第一行输入三个正整数 ( T, K, M )，分别表示询问次数、集合中数的范围和模数。

接下来一行一个长为 ( K-1 ) 的 01 串，串中（从 2 开始计数）第 ( x ) 个数是 1 表示 ( x \in D )，否则 ( x \notin D )。

接下来 ( T ) 行，每行一个正整数 ( n )，表示询问的叶子数量。

输出格式

输出 ( T ) 行，按照询问顺序输出对应的答案。

样例 1

• 输入：

  5 2 47
  1
  1
  2
  3
  4
  5
  

• 输出：

  1
  1
  2
  5
  14
  

说明：此时 ( D = {2} )，答案为卡特兰数 ( C_{n-1} )。

样例 2

• 输入：

  10 15 50
  11101010101101
  1
  2
  3
  4
  5
  10
  100
  10000
  998244353
  1145141919810
  

• 输出：

  1
  1
  3
  11
  44
  27
  31
  30
  10
  26
  

数据范围

对于 100% 的数据：

• ( 1 \le n \le 10^{18} )
• ( 2 \le K, M \le 50 )
• ( 1 \le T \le 100 )

子任务说明：

• 特殊限制 A：( M ) 为质数
• 特殊限制 B：( \gcd(n, M) = 1 )