write a go solution for E2. Deterministic Heap (Hard Version)time limit per test4 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard outputThis is the hard version of the problem. The difference between the two versions is the definition of deterministic max-heap, time limit, and constraints on n and t. You can make hacks only if both versions of the problem are solved.Consider a perfect binary tree with size 2^n-1, with nodes numbered from 1 to 2^n-1 and rooted at 1. For each vertex v (1<=v<=2^n-1-1), vertex 2v is its left child and vertex 2v+1 is its right child. Each node v also has a value a_v assigned to it.Define the operation mathrmpop as follows:  initialize variable v as 1;  repeat the following process until vertex v is a leaf (i.e. until 2^n-1<=v<=2^n-1);   among the children of v, choose the one with the larger value on it and denote such vertex as x; if the values on them are equal (i.e. a_2v=a_2v+1), you can choose any of them;  assign a_x to a_v (i.e. a_v:=a_x);  assign x to v (i.e. v:=x);   assign -1 to a_v (i.e. a_v:=-1). Then we say the mathrmpop operation is deterministic if there is a unique way to do such operation. In other words, a_2vneqa_2v+1 would hold whenever choosing between them.A binary tree is called a max-heap if for every vertex v (1<=v<=2^n-1-1), both a_v>=a_2v and a_v>=a_2v+1 hold.A max-heap is deterministic if the mathrmpop operation is deterministic to the heap when we do it for the first and the second time.Initially, a_v:=0 for every vertex v (1<=v<=2^n-1), and your goal is to count the number of different deterministic max-heaps produced by applying the following operation mathrmadd exactly k times:  Choose an integer v (1<=v<=2^n-1) and, for every vertex x on the path between 1 and v, add 1 to a_x. Two heaps are considered different if there is a node which has different values in the heaps. Since the answer might be large, print it modulo p.InputEach test contains multiple test cases. The first line contains the number of test cases t (1<=t<=50). The description of the test cases follows.The first line of each test case contains three integers n,k,p (2<=n<=100, 1<=k<=500, 10^8<=p<=10^9, p is a prime).It is guaranteed that the sum of n does not exceed 100 and the sum of k over all test cases does not exceed 500.OutputFor each test case, output a single line containing an integer: the number of different deterministic max-heaps produced by applying the aforementioned operation mathrmadd exactly k times, modulo p.ExamplesInput62 1 9982443533 2 9982448533 3 9982443533 4 1000000374 2 1000000394 3 100000037Output2
12
40
100
32
224
Input1100 500 100000037Output66681128
Input287 63 10000003713 437 100000039Output83566569
54517140
NoteFor the first testcase, if we choose v=1 and do the operation, we would have a=[1,0,0], and since a_2=a_3, we can choose either of them when doing the first mathrmpop operation, so such heap is not a deterministic max-heap. And if we choose v=2, we would have a=[1,1,0], during the first mathrmpop, the following would happen:  initialize v as 1  since a_2v>a_2v+1, choose 2v as x, then x=2  assign a_x to a_v, then a=[1,1,0]  assign x to v, then v=2  since v is a leaf, assign -1 to a_v, then a=[1,-1,0] And during the second mathrmpop, the following would happen:  initialize v as 1  since a_2v<a_2v+1, choose 2v+1 as x, then x=3  assign a_x to a_v, then a=[0,-1,0]  assign x to v, then v=3  since v is a leaf, assign -1 to a_v, then a=[0,-1,-1] Since both the first and the second mathrmpop operation are deterministic, this is a deterministic max-heap. Also, if we choose v=3, a would be a deterministic max-heap, so the answer is 2.. Output only the code with no comments, explanation, or additional text.