object BigIntExt {
	implicit def bigintExt(n: BigInt) = new BigIntExt(n)
}
import BigIntExt._
class BigIntExt(n : BigInt) { 
	def **(pow: Int): BigInt =
		if (pow == 0) BigInt(1)
		else if ((pow % 2) == 0) {
			val x = n ** (pow / 2)
			x * x
		}
		else n * (n ** (pow - 1))
}
 
object Main {
	def benchmark(name: String, fun: () => Any) = {
		val t1 = System.currentTimeMillis()
		val res = fun()
		val t2 = System.currentTimeMillis()
		println(name + ": "+(t2 - t1).toFloat/1000 + "sec; Result:"+res.toString())
	}
	def main (args: Array[String]) {
		val test_num = BigInt(2)
		val test_exp = 500000
 
		benchmark("**", () => (test_num ** test_exp) % 1000000)
		benchmark("pow", () => (test_num pow test_exp) % 1000000)
	}
}

b2JqZWN0IEJpZ0ludEV4dCB7CglpbXBsaWNpdCBkZWYgYmlnaW50RXh0KG46IEJpZ0ludCkgPSBuZXcgQmlnSW50RXh0KG4pCn0KaW1wb3J0IEJpZ0ludEV4dC5fCmNsYXNzIEJpZ0ludEV4dChuIDogQmlnSW50KSB7IAoJZGVmICoqKHBvdzogSW50KTogQmlnSW50ID0KCQlpZiAocG93ID09IDApIEJpZ0ludCgxKQoJCWVsc2UgaWYgKChwb3cgJSAyKSA9PSAwKSB7CgkJCXZhbCB4ID0gbiAqKiAocG93IC8gMikKCQkJeCAqIHgKCQl9CgkJZWxzZSBuICogKG4gKiogKHBvdyAtIDEpKQp9CgpvYmplY3QgTWFpbiB7CglkZWYgYmVuY2htYXJrKG5hbWU6IFN0cmluZywgZnVuOiAoKSA9PiBBbnkpID0gewoJCXZhbCB0MSA9IFN5c3RlbS5jdXJyZW50VGltZU1pbGxpcygpCgkJdmFsIHJlcyA9IGZ1bigpCgkJdmFsIHQyID0gU3lzdGVtLmN1cnJlbnRUaW1lTWlsbGlzKCkKCQlwcmludGxuKG5hbWUgKyAiOiAiKyh0MiAtIHQxKS50b0Zsb2F0LzEwMDAgKyAic2VjOyBSZXN1bHQ6IityZXMudG9TdHJpbmcoKSkKCX0KCWRlZiBtYWluIChhcmdzOiBBcnJheVtTdHJpbmddKSB7CgkJdmFsIHRlc3RfbnVtID0gQmlnSW50KDIpCgkJdmFsIHRlc3RfZXhwID0gNTAwMDAwCgkJCgkJYmVuY2htYXJrKCIqKiIsICgpID0+ICh0ZXN0X251bSAqKiB0ZXN0X2V4cCkgJSAxMDAwMDAwKQoJCWJlbmNobWFyaygicG93IiwgKCkgPT4gKHRlc3RfbnVtIHBvdyB0ZXN0X2V4cCkgJSAxMDAwMDAwKQoJfQp9