<s>[INST] Solve $636^{369}\equiv x\pmod{126}$ 
Solve
$$636^{369}\equiv x\pmod{126}$$

My attempt:
$$126=2\times 3^2 \times 7$$
$$\varphi(126)=\varphi(2)\times \varphi(3^2)\times \varphi(7)=36$$
$$\color{gray}{636=6\pmod{126}}$$
$$6^{369}\equiv x \pmod{126}$$
$$2^{369}3^{369}\equiv x \pmod{126}$$
I am stuck here
 [/INST] $636 \equiv 06 \equiv 6 $ (mod 7)
$\varphi(7)=6$
$369 \equiv 09 \equiv 3$ (mod 6)
So
$636^{369}\equiv 6^3 \equiv 36 \times 6 \equiv 6$ (mod 7)
(Note that $gcd(636,7)=1$)
Also, $636\equiv06 \equiv 6$ (mod 9)
and $6\times6=36\equiv 0$ (mod 9)
So
$636^n\equiv 0$ (mod 9) for $n>1$
Therefore, we have $636^{369}=6+7k\equiv 0$ (mod 18)
Hence $k \equiv-\frac{6}{7}\equiv-\frac{42}{7}\equiv-6\equiv12$ (mod 18)
So, finally, $636^{369} =6+7(12+18k')\equiv6+84\equiv90$ (mod 126)
</s>