import java.util.Arrays;

import java.util.List;

import java.util.Random;

import java.util.stream.Collectors;

/**

* Convolution example and test.

*/

public class ConvolutionTest {

public static void main(String[] args) {

Random gen = new Random();

int[] primes = {

1053818881,

1051721729,

1045430273,

1012924417,

1007681537,

1004535809,

998244353,

985661441,

976224257,

975175681,

1000000000 + 7

};

for (int i = 0; i < 1000; i++) {

int mod = primes[gen.nextInt(primes.length)];

int n = gen.nextInt(500) + 1;

int m = gen.nextInt(500) + 1;

long[] a = new long[n];

long[] b = new long[m];

for (int j = 0; j < n; j++) {

a[j] = gen.nextInt(1000000000);

}

for (int j = 0; j < m; j++) {

b[j] = gen.nextInt(1000000000);

}

ModIntFactory factory = new ModIntFactory(mod);

List<ModIntFactory.ModInt> va = Arrays.stream(a).mapToObj(factory::create).collect(Collectors.toList());

List<ModIntFactory.ModInt> vb = Arrays.stream(b).mapToObj(factory::create).collect(Collectors.toList());

long[] expected = Convolution.convolutionNaive(a, b, mod);

long[] actual = Convolution.convolution(va, vb).stream().mapToLong(ModIntFactory.ModInt::value).toArray();

assertArrayEquals(expected, actual);

}

}

private static void assertArrayEquals(long[] expected, long[] actual) {

if (expected.length != actual.length) throw new RuntimeException();

int n = expected.length;

for (int i = 0; i < n; i++) {

if (expected[i] != actual[i]) {

throw new RuntimeException();

}

}

}

}