Codeforces #17 D Notepad

題意﹕求。
看似簡單，但。普通的Repeated Squaring完全不行。
看了一下rng_58的代碼，發覺有一個除了用中國餘式定理以外的做法。

留意﹕若，則有。因此可以用Honor's Rule來算答案。

另，把也是必須的，這步也可以用Honor's Rule來算。

假設，則有，，然後根據這個轉移方程算出，若答案為0則直接輸出。

對於用字串的來算，則找出從最右邊的數位第一個不是0的數位，把它減一，然後把其後的數位取代成9即可。