4769: 放置物品
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：2
解决：1
题目描述
有 $n$ 个位置需要放置物品，要求每个位置放置的物品都不能相同。每个物品以数字进行编号，不同物品的编号是不一样的。每个位置对放置的物品的编号有范围要求，如第 $i$ 个位置放置的物品编号范围是 $1$ 到 $a[i]$ 。
统计有多少放置物品的方案数，答案模1,000,000,009。
统计有多少放置物品的方案数，答案模1,000,000,009。
输入
从文件"fang.in"读入数据。
第一行输入一个正整数 $n$。
第二行输入 $n$ 个正整数，依次表示 $a[i]$。输出
输出到文件"fang.out"中。
输出一行，表示取模后的答案。
样例输入 复制
3
4 7 2样例输出 复制
30提示
对于 $30\%$ 的数据，$ 1 \le n \le 10$，$1 \le a_i \le 10$
对于 $60\%$ 的数据，$ 1 \le n \le 100$，$1 \le a_i \le 100$
对于 $100\%$ 的数据，$ 1 \le n \le 300000$，$1 \le a_i \le 10^9$
对于 $60\%$ 的数据，$ 1 \le n \le 100$，$1 \le a_i \le 100$
对于 $100\%$ 的数据，$ 1 \le n \le 300000$，$1 \le a_i \le 10^9$