Модульная арифметика. Большие числа

[Demonnight]

Здравствуйте! Собственно вот задача:

"Известно, что число 123^137 при делении на m = 13956671042757801363281370296216663 56023102373828208614259008333518048 661758896451829091736021396841, дает в остатке 94824646484608065855902007278075160 27602460059363745767538530725337342 83521476558512528028591507652.
Написать программу, которая находит целое число x такое, что x^137 при делении на то же m, дает в остатке 85385095530186616368924724258647129 86226194726561756402894666898386353 48038838411985760314991260370. Программа должна работать не более 2 минут на ПЭВМ. Число x сохранять в текстовый файл в десятичном виде. Можно пользоваться пакетами программ для работы с большими целыми числами сторонних производителей."

Я использовал теорему Эйлера, но факторизация m занимает много времени (использовались наиболее эффективные алгоритмы - квадратичное решето и решето числового поля).
Подскажите, пожалуйста, решение без использования факторизации.