Can be solved without big mod/fast exponentiation.
Just iterate through the binary string and maintain respective mod values.