write a go solution for E1. Deterministic Heap (Easy Version)time limit per test3 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard outputThis is the easy 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 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<=500). The description of the test cases follows.The first line of each test case contains three integers n,k,p (1<=n,k<=500, 10^8<=p<=10^9, p is a prime).It is guaranteed that the sum of n 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.ExamplesInput71 13 9982443532 1 9982443533 2 9982448533 3 9982443533 4 1000000374 2 1000000394 3 100000037Output1
2
12
52
124
32
304
Input1500 500 100000007Output76297230
Input687 63 10000003777 77 100000039100 200 998244353200 100 99824435332 59 9982448531 1 998244353Output26831232
94573603
37147649
847564946
727060898
1
NoteFor the first testcase, there is only one way to generate a, and such sequence is a deterministic max-heap, so the answer is 1.For the second 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] Since the first mathrmpop operation is 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.