# [Solution] Sum of Product 2 solution codechef

Sum of Product 2 solution codechef – For an array A of length N, let F(A) denote the sum of the product of all the subarrays of A. Formally,

## [Solution] Sum of Product 2 solution codechef

F(A) = \sum_{L=1}^N \sum_{R=L}^N \left (\prod_{i=L}^R A_i\right )

For example, let A = [1, 0, 1], then there are 6 possible subarrays:

• Subarray [1, 1] has product = 1
• Subarray [1, 2] has product = 0
• Subarray [1, 3] has product = 0
• Subarray [2, 2] has product = 0
• Subarray [2, 3] has product = 0
• Subarray [3, 3] has product = 1

So F(A) = 1+1 = 2.

Given a binary array A, determine the sum of F(A) over all the N! orderings of A modulo 998244353.

Note that orderings here are defined in terms of indices, not elements; which is why every array of length N has N! orderings. For example, the 3! = 6 orderings of A = [1, 0, 1] are:

• [1, 0, 1] corresponding to indices [1, 2, 3]
• [1, 1, 0] corresponding to indices [1, 3, 2]
• [0, 1, 1] corresponding to indices [2, 1, 3]
• [0, 1, 1] corresponding to indices [2, 3, 1]
• [1, 1, 0] corresponding to indices [3, 1, 2]
• [1, 0, 1] corresponding to indices [3, 2, 1]

## [Solution] Sum of Product 2 solution codechef

• The first line of input will contain a single integer T, denoting the number of test cases.
• Each test case consists of multiple lines of input.
• The first line of each test case contains a single integer N denoting the le
• The second line contains N space-separated integers denoting the array A.

### Output Format

For each test case, output the sum of F(A) over all the N! orderings of A, modulo 998244353.

### Constraints

• 1 \leq T \leq 1000
• 1 \leq N \leq 10^5
• 0 \leq A_i \leq 1
• The sum of N over all test cases won’t exceed 2 \cdot 10^5.

## [Solution] Sum of Product 2 solution codechef

Input

Output

4
3
1 0 1
1
0
2
1 1
4
1 1 0 1

16
0
6
120