   return ans;
 }
 
-void bit_reverse_copy(vector<LL> &a, vector<LL> &A, int n) {
-  A.resize(a.size());
-  for (int i = 0; i < a.size(); i++)
+void bit_reverse_copy(LL *a, LL *A, int n, int size) {
+  for (int i = 0; i < size; i++)
     A[bit_reverse(i, n)] = a[i];
 }
 
-vector<LL> compute_powers(int ln, LL basew, LL prime){
-  vector<LL> powers(ln);
+void compute_powers(LL *powers, int ln, LL basew, LL prime){
   powers[0] = basew;
   for (int i = 1; i < ln; i++){
     powers[i] = (powers[i - 1] * powers[i - 1]) % prime;
   }
-  return powers;
-}
-
-vector<LL> fft(vector<LL> &a, int dir, LL prime, LL basew) {
-  int ln = ceil(log2(float(a.size())));
-  vector<LL> A;
-  bit_reverse_copy(a, A, ln);
-  vector<LL> powers = compute_powers(ln, basew, prime);
+}
+
+void fft(LL *a, LL *A, int dir, LL prime, LL basew, int size) {
+  int ln = ceil(log2(float(size)));
+  bit_reverse_copy(a, A, ln, size);
+  LL *powers = (LL*) malloc (sizeof (LL) * ln);
+  compute_powers(powers, ln, basew, prime);
 
   for (int s = 1; s <= ln; s++) {
     long long m = (1LL << s);
     LL wm = powers[ln - s];
-    //cout << wm << endl;
     if (dir == -1)
       wm =  mod_inv(wm, prime);
 
-    for (int k = 0; k < a.size(); k += m) {
+    for (int k = 0; k < size; k += m) {
       LL w = 1, mh = m >> 1;
       for (int j = 0; j < mh; j++) {
         LL t = (w * A[k + j + mh]) % prime;

            make_pair(754974721,643797295), make_pair(1107296257,883865065)};

PLL ROU_2[] = {make_pair(1711276033LL, 1223522572LL), make_pair(1790967809LL, 1110378081LL)};

PLL ext_euclid(LL a, LL b) {
  if (b == 0)

  }

  if (dir < 0) {
    LL in = mod_inv(size, prime);
    for (int i = 0; i < size; i++)
      A[i] = (A[i] * in) % prime;
  }
}

__device__ void d_ext_euclid(LL a, LL b, LL &x, LL &y, LL &g) {
