write a go solution for C. Beautiful Sequencetime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputLet's call an integer sequence beautiful if the following conditions hold:   its length is at least 3;  for every element except the first one, there is an element to the left less than it;  for every element except the last one, there is an element to the right larger than it; For example, [1,4,2,4,7] and [1,2,4,8] are beautiful, but [1,2], [2,2,4], and [1,3,5,3] are not.Recall that a subsequence is a sequence that can be obtained from another sequence by removing some elements without changing the order of the remaining elements.You are given an integer array a of size n, where every element is from 1 to 3. Your task is to calculate the number of beautiful subsequences of the array a. Since the answer might be large, print it modulo 998244353.InputThe first line contains a single integer t (1<=t<=10^4) — the number of test cases.The first line of each test case contains a single integer n (3<=n<=2*10^5).The second line contains n integers a_1,a_2,...,a_n (1<=a_i<=3).Additional constraint on the input: the sum of n over all test cases doesn't exceed 2*10^5.OutputFor each test case, print a single integer — the number of beautiful subsequences of the array a, taken modulo 998244353.ExampleInput473 2 1 2 2 1 343 1 2 231 2 391 2 3 2 1 3 2 2 3Output3
0
1
22
NoteIn the first test case of the example, the following subsequences are beautiful:  [a_3,a_4,a_7];  [a_3,a_5,a_7];  [a_3,a_4,a_5,a_7].. Output only the code with no comments, explanation, or additional text.