TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P2040
  • 题目
  • P2040【CQOI2011】放棋子
    限制 : 时间限制 : 10000 MS   空间限制 : 165536 KB
    问题描述

    在一个n行m列的棋盘里放一些彩色的棋子,使得每个格子最多放一个棋子,且不同颜色的棋子不能在同一行或者同一列。有多少种方法? 例如,n=m=3,有两个白棋子和一个灰棋子,下面左边两种方法都是合法的,但右边两种都是非法的。

    输入格式

    输入第一行为两个整数n, m, c,即行数、列数和棋子的颜色数。第二行包含c个正整数,即每个颜色的棋子数。所有颜色的棋子总数保证不超过nm。

    输出格式

    输出仅一行,即方案总数除以 1,000,000,009的余数。

    样例输入

    样例输入1:
    5 2 3
    1 1 1

    样例输入2:
    4 2 2
    3 1

    样例输入3:
    8 8 8
    1 1 1 1 1 1 1 1

    样例输出

    样例输出1:
    0

    样例输出2:
    8

    样例输出3:
    625702391

    提示


    数据范围
    编号 1-2 3-5 6-7 8-10
    n, m <=4 <=10 <=30 <=30
    c <=2 <=5 <=2 <=10
    总棋子数 <=5 <=20 <=900 <=250