Object Math {

  def modpow(base:int, power:int, mod:int):Int = modpow(base, power, mod, 1)

  private[this] def modpow(base:int, power:int, mod:int, curr:int):int= power match {
    case 0 => curr
    case _ => {
      val n = if ((power & 1)==1) (curr * base) % mod else curr
      modpow((base * base) % mod, power >>1, mod, n)
    }
  }
}