Of course there's a Fast Fourier Transform problem in this contest! There may be number theory involved!

vector<int> f(int n)

You may assume ~1 \le n \le 10^6~ - though in practice there is only one test case, so maybe you can guess the value of ~n~ beforehand!