I compiled my code on ideone and there I have 0.4 sec for test 1800 10
So I have tle 9. Maybe there are stronger tests?
By the way my program use vectors in long arithmetics. Should I use strings in it?

Edited by author 08.05.2017 22:14

My solution in Python 3.4 solves the problem in 78 milliseconds.
I do not use binary power.