## GUPTA MECHANICAL

IN THIS WEBSITE I CAN TELL ALL ABOUT TECH. TIPS AND TRICKS APP REVIEWS AND UNBOXINGS ALSO TECH. NEWS .............

# [Solution] Sum of Product 2 CodeChef Solution 2022

## Problem

For an array $A$ of length $N$, let $F(A)$ denote the sum of the product of all the subarrays of $A$. Formally,

$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$.

Solution Click Below:-  👉
👇👇👇👇👇

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]$

### Input Format

• 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$.