Type: Default 1000ms 256MiB

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

问题描述

nn 个点,编号为 1,2,3,,n1,2,3,\cdots,n。求连一些边权是 11 的边,使得图满足以下性质的方案数:

  1. 没有重边和自环。
  2. ii 个点的度数是 did_i
  3. 对于 1<in1<i\leq n, 11ii 存在唯一一条最短路。
  4. lil_i11ii 的最短路长度,对于 1<i<n1<i<n,满足 lili+1l_i\leq l_{i+1}

输入格式

第一行一个整数: nn

第二行 nn 个整数:d1,d2,,dnd_1,d_2,\cdots,d_n

输出格式

输出一行表示答案。对 109+710^9+7 取模。

5 
2 3 3 2 2
2

数据范围

所有数据保证 3n1000,2di33\leq n\leq 1000,2\leq d_i\leq 3

测试点编号 nn 测试点编号 nn
11 5\leq 5 1313 =15=15
242-4 50\leq 50 14,1514,15 =20=20
585-8 300\leq 300 161816-18 =40=40
9,109,10 1000\leq 1000 19,2019,20 =50=50
1111 =10=10 21,2221,22 =100=100
1212 =12=12 232523-25 =300=300

虚假的比赛

Not Attended
Status
Done
Rule
IOI
Problem
4
Start at
2023-10-6 8:00
End at
2023-10-7 8:00
Duration
24 hour(s)
Host
Partic.
56