write a go solution for F. Count Leavestime limit per test4 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputLet n and d be positive integers. We build the the divisor tree T_n,d as follows:  The root of the tree is a node marked with number n. This is the 0-th layer of the tree.  For each i from 0 to d-1, for each vertex of the i-th layer, do the following. If the current vertex is marked with x, create its children and mark them with all possible distinct divisors^dagger of x. These children will be in the (i+1)-st layer.  The vertices on the d-th layer are the leaves of the tree. For example, T_6,2 (the divisor tree for n=6 and d=2) looks like this:  Define f(n,d) as the number of leaves in T_n,d.Given integers n, k, and d, please compute sumlimits_i=1^nf(i^k,d), modulo 10^9+7.^dagger In this problem, we say that an integer y is a divisor of x if y>=1 and there exists an integer z such that x=y*z.InputEach test contains multiple test cases. The first line contains the number of test cases t (1<=t<=10^4). The description of the test cases follows.The only line of each test case contains three integers n, k, and d (1<=n<=10^9, 1<=k,d<=10^5).It is guaranteed that the sum of n over all test cases does not exceed 10^9.OutputFor each test case, output sumlimits_i=1^nf(i^k,d), modulo 10^9+7.ExampleInput36 1 11 3 310 1 2Output14
1
53
NoteIn the first test case, n=6, k=1, and d=1. Thus, we need to find the total number of leaves in the divisor trees T_1,1, T_2,1, T_3,1, T_4,1, T_5,1, T_6,1.  T_1,1 has only one leaf, which is marked with 1.  T_2,1 has two leaves, marked with 1 and 2.  T_3,1 has two leaves, marked with 1 and 3.  T_4,1 has three leaves, marked with 1, 2, and 4.  T_5,1 has two leaves, marked with 1 and 5.  T_6,1 has four leaves, marked with 1, 2, 3, and 6. The total number of leaves is 1+2+2+3+2+4=14.In the second test case, n=1, k=3, d=3. Thus, we need to find the number of leaves in T_1,3, because 1^3=1. This tree has only one leaf, so the answer is 1.. Output only the code with no comments, explanation, or additional text.