Chef and Horcrux

All submissions for this problem are available.
Read problems statements in mandarin chinese, russian and vietnamese as well.
Once again Harry is out there with his friends Ron and Hermione looking out for Horcruxes. They found out that one of the Horcrux is located at The Lestrange Vault. But YouKnowWho has locked the vault with a dark spell.
Fortunately, the password to the vault can be found out by solving a problem. But they were not able to solve the problem and hence need help from Chef. Since Chef is quite busy, he has delegated this task to you.
You are given an array of N elements. MEX of a set is defined as the minimum nonnegative integer that doesn't exist in it. For example, the MEX of the set {0, 2, 4} is 1 and the MEX of the set {1, 2, 3} is 0. Note that the MEX of empty set will be 0.
Similar to Expected value, let's define Cheftated value, C[Y] of a random variable Y as follows: where Y is a random variable with a finite number of outcomes y_{1}, y_{2}, ..... , y_{a} occurring with probabilities p_{1}, p_{2}, ..... , p_{a}. Take 0^{0} = 1.
You are given an array A consisting of N nonnegative integers. Your task is to calculate the cheftated value of base K xor sum of MEX values of X randomly selected subsequences( repetitions allowed) of A.
Cheftated value can always be represented as an irreducible fraction P/Q such that gcd(Q, 330301441) = 1, i.e. Q^{1} ( multiplicative inverse) modulo 330301441 exists. You have to print the value P * Q^{1} modulo 330301441. Please see the sample explanation for more details.
Also, xorsum in base K (xor_{k}) can be perfomed by representing the numbers in base K and adding each digit in base K( without carrying forward), e.g. xorsum of 6 and 9 in base 5 is equal to 11_{5} xor_{5} 14_{5} = 20_{5}, i.e. the number 10.
Input
First line of the input contains an integer T denoting number of test cases.
First line of each test case contains three space separated integers N, K and X.
Second line of each test case contains N space separated integers, ith of which is A_{i} denoting the i^{th} element of the array.
Output
For each test case, output a line containing single integer representing the value of P*Q^{1} modulo 330301441.
Constraints
 1 ≤ T ≤ 5
 1 ≤ N ≤ 10^{5}
 2 ≤ K ≤ 10
 2 ≤ X ≤ 10^{18}
 0 ≤ A_{i} ≤ 10^{5}
Subtasks
 Subtask #1 (15 points) : K ≤ 3
 Subtask #2 (15 points) : N ≤ 10^{3}
 Subtask #3 (70 points) : Original constraints
Example
Input: 2 3 2 2 1 0 2 4 4 4 4 0 1 1 Output: 87392358 88861416
Explanation
Example case 1: Let's name the subsequences as A = [], B = [1], C = [0], D = [2], E = [1, 0], F = [1, 2], G = [0, 2], H = [1, 0, 2].
Possible outcome of xor values after selecting two subsequences (repetitions allowed):
 0 when you select (two from (A, B, D, F)) or (two from (C, G)) or (two from (E)) or (two from (H)) making it 22 ways.
 1 when you select (one from (A, B, D, F) and one from (C, G)) or (one from (E) and one from (H)) making it 18 ways.
 2 when you select (one from (A, B, D, F) and one from (E)) or (one from (H) and one from (C, G)) making it 12 ways.
 3 when you select (one from (A, B, D, F) and one from (H)) or (one from (E) and one from (C, G)) making it 12 ways.
Cheftated value = 0^{2*0} * (22/64)^{3*0} + 1^{2*1} * (18/64)^{3*1} + 2^{2*2} * (12/64)^{3*2} + 3^{2*3} * (12/64)^{3*3} = 70310425195/68719476736.
Answer to print = 70310425195 * 68719476736^{1} mod 330301441 = 87392358
Author:  adkroxx 
Tester:  alex_2oo8 
Editorial  https://discuss.codechef.com/problems/XORTREEH 
Tags  adkroxx, fastexpo, fastmodexp, fft, hard, ntt, oct17 
Date Added:  23082017 
Time Limit:  5 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.5, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, kotlin, PERL6, TEXT, SCM chicken, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 