primes – Central Trinomial Coefficients best time complexity

What is the fastest known time complexity for computing central trinomial coefficients?

Let $$C_n=1,1,3,7,19,51,…$$ (OEIS A002426) denote the coefficient of $$x^n$$ in $$(x^2+x+1)^n$$ starting at $$n=0$$.

It can be shown that, if $$n$$ is prime, then $$C_n=1 pmod n$$, because by the binomial theorem

$$(x + y)^n=sum_{k=0}^{n} binom{n}{k}y^kx^{n-k}=x^n+y^npmod n$$ so that

$$(x^2+x+1)^n = x^2+x+1pmod n$$

follows.

The computational complexity problem I am aiming on solving is, given a large integer $$n$$ (say, about RSA size), I would like to verify that the congruence

$$C_n=1pmod n$$

in polynomial time analogous to how $$x^n=x pmod n$$ can be computed using binary exponentiation.

Thanks for help.