\(f, g\) を高々 \(N\) 次の多項式としたときの \([x^M] f(x) / g(x)\) を求めたい。分母分子に \(g(-x)\) を掛けて
$$[x^M]\frac{f(x)}{g(x)} = [x^M]\frac{f(x)g(-x)}{g(x)g(-x)}$$ とすると、\(g(x)g(-x)\) は偶関数なので高々 \(N\) 次の多項式 \(G\) を用いて \(g(x)g(-x) = G(x^2)\) とできる（ここが本質）。\(f(x)g(-x) = h_1(x^2) + x h_2(x^2)\) と分けると、\(M\) の偶奇に従って、どちらか一方だけを調べればよい。再帰的に処理すると \(O(\mathrm{M}(N) \log(M))\) になる。

long kth(long[] f, long[] g, long n) {
  if (f.length == 0) return 0;
  if (n == 0) return f[0] * inv(g[0]);
  long[] flipg = IntStream.range(0, g.length).mapToLong(i -> i % 2 == 0 ? g[i] : -g[i]).toArray();
  long[] a = mul(f, flipg);
  long[] b = mul(g, flipg);
  long[] ae = IntStream.range(0, a.length).filter(i -> i%2 == 0).mapToLong(i -> a[i]).toArray();
  long[] ao = IntStream.range(0, a.length).filter(i -> i%2 == 1).mapToLong(i -> a[i]).toArray();
  long[] be = IntStream.range(0, b.length).filter(i -> i%2 == 0).mapToLong(i -> b[i]).toArray();
  if (n % 2 == 0) {
    return kth(ae, be, n / 2);
  } else {
    return kth(ao, be, (n - 1) / 2);
  }
}