C言語で多倍長演算を実装してる途中で、あまりに面倒くさくなったので、 今回はPythonです。 http://codepad.org/iqjwda6Tオーバーフローを気にしなくて良いというのが嬉しいですね。

http://codepad.org/yk4p68Hfintでもlong long intでも50回回してたらオーバーフローしてしまったので、 半分の25回だけにしたところ正しいと判定されたので、 それを答えとします。