Tree Selection with Prescribed Degrees

You are given ( n ) nodes, numbered from 1 to ( n ). Each node ( i ) has an associated weight ( v_i ). You are asked to select a nonempty subset ( S = {d_1,d_2,\dots,d_m} ) (where ( 1\le m\le n )) of nodes such that these nodes can form a tree and furthermore, for every node ( d_i ) in ( S ), its degree in the tree is exactly ( v_{d_i} ). In a tree, the degree of a node is defined as the number of nodes adjacent to it.

Note that a tree with one node has degree 0, so if ( m=1 ) then the only chosen node must have ( v=0 ); and if ( m \ge 2 ) then every chosen node must have ( v\ge1 ) and, trivially, ( v\le m-1 ) (since the maximum degree in a tree on ( m ) nodes is ( m-1 )).

A necessary condition for such a tree to exist is that the sum of degrees equals twice the number of edges, that is: [ \sum_{i\in S} v_i = 2(m-1). ]

It is known that if ( v_1,v_2,\dots,v_m ) are positive integers (or 0 in the case of a singleton) satisfying ( \sum_{i=1}^{m} v_i=2(m-1) ) and ( v_i \le m-1 ) for every ( i ) (when ( m\ge2 )), then the sequence is a tree degree sequence. Moreover, the number of labeled trees having the prescribed degree sequence ( (v_{d_1},v_{d_2},\dots,v_{d_m}) ) is given by the formula: [ \frac{(m-2)!}{\prod_{i=1}^{m} (v_{d_i}-1)!},] with the convention that when ( m=1 ) a single valid tree exists if and only if ( v=0 ).

Your task is to compute the total number of schemes. A scheme is defined by a valid subset ( S ) along with a valid tree on ( S ) that verifies the above degree condition. Since the answer can be very large, output it modulo ( 998244353 ).

inputFormat

The first line contains a single integer ( n ) ( (1 \le n \le 20) ) representing the number of nodes. The second line contains ( n ) space‐separated integers ( v_1,v_2,\dots,v_n ) where each ( v_i ) is the weight of the ( i )th node.

outputFormat

Output a single integer, the total number of valid schemes modulo ( 998244353 ).

sample

1
0

1