#P2476. [SCOI2008] 着色方案

    ID: 1484 远端评测题 1000ms 125MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>动态规划dp搜索2008四川各省省选记忆化搜索

[SCOI2008] 着色方案

题目描述

nn 个木块排成一行,从左到右依次编号为 11nn

你有 kk 种颜色的油漆,第 ii 种颜色的油漆足够涂 cic_i 个木块。

所有油漆刚好足够涂满所有木块,即 i=1kci=n\sum_{i=1}^kc_i=n

由于相邻两个木块涂相同色显得很难看,所以你希望统计任意两个相邻木块颜色不同的着色方案。

由于答案可能很大,请输出对 109+710^9+7 取模的结果。

输入格式

第一行,一个整数 kk,表示颜色数量。

第二行 kk 个整数 c1,c2,,ckc_1,c_2,\dots,c_k,表示每种颜色能够涂木块的个数。

输出格式

一行一个整数,表示答案对 109+710^9+7 取模的结果。

3
1 2 3
10
5
2 2 2 2 2
39480
10
1 1 2 2 3 3 4 4 5 5

85937576

提示

  • 对于 50%50\% 的数据,1k51 \leq k \leq 51ci31 \leq c_i \leq 3
  • 对于 100%100\% 的数据,1k151 \leq k \leq 151ci51 \leq c_i \leq 5