该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

说明

本题不再额外提供样例文件。

题目描述

有一个 $M×N$ 的网格图。现在让你将其中的一些格子涂上颜色。一共给了你 $K$ 种颜色的画笔，要求使用第 $i$ 种颜色涂 $X_i$ 个格子，一个格子最多只能涂一种颜色，同一行的格子只能涂相同的颜色，同一列的格子也只能涂相同的颜色。

问：有多少种涂色方案？

答案可能很大，你需要输出答案 mod $(10^9+9)$，其中 $10^9+9$ 是一个质数。

输入

第一行：三个整数 $N, M, K$

第二行：$K$ 个正整数 $X_i$。

输出

一个整数，表示方案数 mod $(10^9+9)$。

样例1输入

3 2 2                   
2 1

样例1输出

6

样例2输入

30 20 10                   
1 2 3 4 5 6 7 8 9 10

样例2输出

346218356

数据范围

100% 的数据：$1 ≤ N, M ≤ 30$，$1 ≤ K ≤ 10$，$1 ≤ Σ X_i ≤ N·M$。