#P2476. [SCOI2008] 着色方案
[SCOI2008] 着色方案
题目描述
有 个木块排成一行,从左到右依次编号为 至 。
你有 种颜色的油漆,第 种颜色的油漆足够涂 个木块。
所有油漆刚好足够涂满所有木块,即 。
由于相邻两个木块涂相同色显得很难看,所以你希望统计任意两个相邻木块颜色不同的着色方案。
由于答案可能很大,请输出对 取模的结果。
输入格式
第一行,一个整数 ,表示颜色数量。
第二行 个整数 ,表示每种颜色能够涂木块的个数。
输出格式
一行一个整数,表示答案对 取模的结果。
3
1 2 3
10
5
2 2 2 2 2
39480
10
1 1 2 2 3 3 4 4 5 5
85937576
提示
- 对于 的数据,,;
- 对于 的数据,,。