Sereja and Tree
All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian.
Sereja likes to hang around trees. A tree is an undirected graph on N vertices with N-1 edges and no cycles. Sereja has his own peculiar way of comparing two trees. To describe it, let's start with the way Sereja stores a tree. For every tree, Sereja has a value V — the root of the tree, and for every vertex i, he has an ordered list Q[i] with L[i] elements — Q[i], Q[i], ..., Q[i][L[i]] which are children of the vertex i. Sereja assumes two trees to be equal if their roots are the same and for every i, the ordered list Q[i] is the same in both the trees that Sereja compares.
So if Sereja has tree#1 given as [V=1, Q=[2, 3], Q=, Q=] and tree#2 given as [V=1, Q=[3, 2], Q=, Q=], they will be considered different because Q in the first tree is not equal to Q in the second tree.
For any vertex i, Sereja calls number of vertices adjacent to it as E[i].
Given an array C of N elements, Let f(C) be the number of different trees (in Sereja's representation) such that there exists a permutation P, P, ... , P[N] so that E[P]=C, E[P]= C, ... , E[P[N]]=C[N].
Sereja gives you the array C. You have to compute the number f(C) modulo 1000000007 (109+7).
InputThe first line of input contains the integer N. Next line contains N integers C, C, ..., C[N].
OutputOutput answer in single line.
- 1 ≤ N ≤ 80
- 0 ≤ C[i] ≤ 80
Input: 4 1 1 2 2 Output: 72 Input: 5 3 1 1 1 2 Output: 960 Input: 3 2 2 2 Output: 0
|Tags||cook64, dynamic-programming, hard, mathematics, memoization, sereja, tree|
|Time Limit:||10 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.