Genos is obsessed with counting and spends all his time doing it. To test his abilities, master Saitama gave him a binary string $$$a$$$ and asked him to calculate a function $$$g(a)$$$.
For any array $$$b$$$ of length $$$m$$$, let $$$f(b)$$$ denote an array $$$c$$$ of length $$$m$$$ such that: $$$$$$ \text{for each } i \, (1 \le i \le m), \quad c_i \text{ is the number of indices } j \text{ such that } 1 \le j \lt i \text{ and } b_j \gt b_i. $$$$$$ If $$$b$$$ is a binary string, consider its characters as integers (i.e., '0' as $$$0$$$ and '1' as $$$1$$$).
Now, $$$g(b)$$$ is defined as the sum of all elements of the array $$$f(f(b))$$$.
You are another disciple of master Saitama. To prove your superiority over Genos, you decide to calculate the sum of $$$g(a)$$$ over all distinct permutations of the given binary string $$$a$$$. Since the answer can be very large, output it modulo $$$998{,}244{,}353$$$.
A permutation of an array or string is any reordering of its elements.
Two permutations are considered different if and only if there exists at least one index $$$i$$$ such that the element at position $$$i$$$ differs between the two permutations. For example, the permutations $$$[0, 1, \textit{1}]$$$ and $$$[0, \textit{1}, 1]$$$ are not considered distinct, since swapping identical elements does not create a new array.
The first line of the input contains a single integer $$$t$$$ ($$$1 \le t \le 10^5$$$) — the number of test cases.
The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the length of the string $$$a$$$.
The second line of each test case contains a binary string $$$a$$$ of length $$$n$$$ ($$$a_i$$$ is either '0' or '1').
It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.
For each test case, output a single integer in a line — the sum of $$$g(a)$$$ over all distinct permutations of $$$a$$$, modulo $$$998{,}244{,}353$$$.
2 1 4 -1 4 -7 7 -8 -1 -5 3 2 6 2 3 0 0 1 1 1 0 0 1 -1 -1
0 0
In the first sample test case where $$$a = 0011$$$, there are $$$6$$$ distinct permutations of $$$a$$$. For each permutation $$$a_i$$$, the value of $$$g(a_i)$$$ is shown in the following table:
| $$$i$$$ | $$$a_i$$$ | $$$g(a_i)$$$ |
| $$$1$$$ | $$$[0, 0, 1, 1]$$$ | $$$0$$$ |
| $$$2$$$ | $$$[0, 1, 0, 1]$$$ | $$$1$$$ |
| $$$3$$$ | $$$[0, 1, 1, 0]$$$ | $$$0$$$ |
| $$$4$$$ | $$$[1, 0, 0, 1]$$$ | $$$2$$$ |
| $$$5$$$ | $$$[1, 0, 1, 0]$$$ | $$$1$$$ |
| $$$6$$$ | $$$[1, 1, 0, 0]$$$ | $$$0$$$ |
The sum of $$$g(a_i)$$$ over all distinct permutations is: $$$\sum_{i=1}^{6} g(a_i) = 0 + 1 + 0 + 2 + 1 + 0 = 4$$$.
