Rookhopper's Tour

Rookhopper's Tour

题号：NC276703
时间限制：C/C++/Rust/Pascal 4秒，其他语言8秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

给定正整数 $n,m$ ，设二元组集合 $S=\{(x,y)\mid 1\le x\le n;1\le y\le m;x,y\in \mathbb{Z}\}$ 。你需要选择 $S$ 的一个子集 $T$ ，使得：

对于任意 $(x_1,y_1),(x_2,y_2)\in T$ ，要么 $(x_1,y_1)=(x_2,y_2)$ ，要么 $x_1\neq x_2,y_1\neq y_2$ ；
对于任意 $(x,y)\in T$ ，存在 $(x',y')\in T$ ，满足 $|x-x'|=1$ 或 $|y-y'|=1$ 。

有 $q$ 次询问，第 $i$ 次给定正整数 $k_i$ ，求有多少种选择 $T$ 的方案，使得 $T$ 满足上述条件，且 $|T|=k_i$ 。答案对 $10^9+7$ 取模。

输入描述:

第一行，三个正整数 $n,m,q$ 。

第二行， $q$ 个正整数 $k_1,k_2,\dots,k_q$ 。

输出描述:

一行， 个非负整数，表示答案。

示例1

输入

复制

2 2 2
1 2

输出

复制

0 2

说明

有三种选择  的方案：，其中  的有  种， 的有  种。

示例2

输入

复制

3 4 3
1 2 3

输出

复制

0 30 24

示例3

输入

复制

654321 123456 5
1 2 3 4 5

输出

复制

0 84994385 800381083 658879412 585470103

备注:

；
；
。