CF1517E Group Photo

In the 2050 Conference, some people from the competitive programming community meet together and are going to take a photo. The $ n $ people form a line. They are numbered from $ 1 $ to $ n $ from left to right. Each of them either holds a cardboard with the letter 'C' or a cardboard with the letter 'P'. Let $ C=\{c_1,c_2,\dots,c_m\} $ $ (c_1

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 200\,000 $ ). Description of the test cases follows. The first line of each test case contains a single integer $ n $ ( $ 1\leq n\leq 200\,000 $ ). The second line contains $ n $ integers $ a_1, a_2, \ldots, a_n $ ( $ 1 \le a_i \le 10^9 $ ). It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 200\,000 $ .

For each test case, output the answer modulo $ 998\,244\,353 $ in a separate line.

For the first test case, there are $ 10 $ possible good photos satisfying the condition: PPPPP, CPPPP, PCPPP, CCPPP, PCCPP, PCPCP, PPPPC, CPPPC, PCPPC, PPPCC. For the second test case, there are $ 7 $ possible good photos satisfying the condition: PPPP, PCPP, PCCP, PPPC, PCPC, PPCC, PCCC.