题目描述

小L在爬一个有 $n$ 阶的楼梯，他有 $m$ 种爬楼梯的方式，请你回答他 $q$ 个问题，每个问题以 $b_{i}$ 的形式给出，请你回答到第 $b_{i}$ 个楼梯的方式有多少种，请你将答案对 $10^9 + 7$ 取模。

输入格式

第一行输入三个整数 $n,m,q\ (1 \leq n ,m,q \leq 5000)$；

第二行输入 $m$ 个数，第 $i$ 个数 $a_{i}\ (1 \leq a_i \leq n)$ 表示一次可以跳 $a_{i}$ 个阶梯；

第三行输入 $q$ 个数，第 $i$ 个数 $b_{i}\ (1 \leq b_i \leq n)$ 表示第 $i$ 次询问。

输出格式

输出一行一共 $q$ 个数以空格作为间隔，第 $i$ 个数表示第 $i$ 次询问的答案。

输入输出样例 #1

输入 #1

3 2 2
1 2
3 2

输出 #1

3 2

说明/提示

到第 $3$ 个台阶有 $[1,3]$、$[2,3]$、[$1,2,3]$ 三种跳法。

到第 $2$ 个台阶有 $[1,2]$、$[2]$ 两种跳法。