The value of $k$ can be very large indeed (up to $10^{12}$). Is there an efficient way to calculate the output?

Edit : 'm' is a prime number.