Calculate the remainder

The problem is similar to finding $\left(7^{123} + 9^{123}\right) \bmod 64$ .

$\begin{aligned} 7^{123} + 9^{123} & \equiv \left((8-1)^{123} + (8+1)^{123}\right) \text{ (mod 64)} \\ & \equiv 2 \left(8^{123} + \frac {123\cdot 122}2 \cdot 8^{121} + \cdots + \frac {123\cdot 122 \cdot 121}{1\cdot 2\cdot 3}\cdot 8^3+ 123\cdot 8 \right) \text{ (mod 64)} \\ & \equiv 2 \cdot 123\cdot 8 \text{ (mod 64)} \\ & \equiv 2(-5)(8) \text{ (mod 64)} \\ & \equiv -80 \text{ (mod 64)} \\ & \equiv -16 \text{ (mod 64)} \\ & \equiv \boxed{48} \text{ (mod 64)} \end{aligned}$