rt，这份代码能过：

#include <iostream>
#include <string>
#include <bitset>
#include <type_traits>
#include <cstdint>
#include <cstdlib>
#include <cstddef>
#include <algorithm>
#include <random>
namespace std {
template <typename _Tp>
constexpr int __countr_zero(_Tp __x) noexcept {
    constexpr auto _Nd = numeric_limits<_Tp>::digits;
    if (__x == 0) return _Nd;
    constexpr auto _Nd_ull = numeric_limits<unsigned long long>::digits;
    constexpr auto _Nd_ul = numeric_limits<unsigned long>::digits;
    constexpr auto _Nd_u = numeric_limits<unsigned>::digits;
    if (_Nd <= _Nd_u) return __builtin_ctz(__x);
    if (_Nd <= _Nd_ul) return __builtin_ctzl(__x);
    if (_Nd <= _Nd_ull) return __builtin_ctzll(__x);
    static_assert(_Nd <= (2 * _Nd_ull), "Maximum supported integer size is 128-bit");
    constexpr auto __max_ull = numeric_limits<unsigned long long>::max();
    unsigned long long __low = __x & __max_ull;
    if (__low != 0) return __builtin_ctzll(__low);
    unsigned long long __high = __x >> _Nd_ull;
    return __builtin_ctzll(__high) + _Nd_ull;
}
}
template <__uint128_t __mod, bool __isprime = true>
class DynamicModInt {
public:
    using u32 = uint64_t;
    using i64 = __int128_t;
    using u64 = __uint128_t;
    using m64 = DynamicModInt;
    using value_type = u64;
    static inline u64 mod() { return s_mod; }
    static inline u64 get_primitive_root_prime() {
    	if (!s_isPrime) return 0;
        u64 tmp[500] = {};
        u64 cnt = 0;
        const u64 phi = s_mod - 1;
        u64 m = phi;
        for (u64 i = 2; i * i <= m; ++i) {
            if (m % i == 0) {
                tmp[cnt++] = i;
                do m /= i;
                while (m % i == 0);
            }
        }
        if (m != 1) tmp[cnt++] = m;
        for (m64 res = 2;; res += 1) {
            bool f = true;
            for (int i = 0; i < cnt && f; ++i) f &= res.pow(phi / tmp[i]) != 1;
            if (f) return u64(res);
        }
    }
    constexpr DynamicModInt() : v_() {}
    ~DynamicModInt() = default;
    template <typename T, typename std::enable_if<std::is_arithmetic<T>::value || std::is_same<T, i64>::value || std::is_same<T, u64>::value, int>::type = 0>
    inline DynamicModInt(T v) : v_(reduce(mul(norm(v % i64(s_mod)), r2))) {}
    constexpr DynamicModInt(const m64 &) = default;
    inline u64 val() const { return reduce({0, v_}); }
    template <typename T, typename std::enable_if<std::is_arithmetic<T>::value || std::is_same<T, i64>::value || std::is_same<T, u64>::value, int>::type = 0>
    explicit constexpr operator T() const { return T(val()); }
    inline m64 operator-() const {
        m64 res;
        res.v_ = (s_mod & -(v_ != 0)) - v_;
        return res;
    }
    inline m64 inv_exgcd() const {
        i64 x1 = 1, x3 = 0, a = val(), b = s_mod;
        while (b != 0) {
            i64 q = a / b, x1_old = x1, a_old = a;
            x1 = x3, x3 = x1_old - x3 * q, a = b, b = a_old - b * q;
        }
        return m64(x1);
    }
    inline m64 inv_fermat() const { return pow(s_mod - 2); }
    inline m64 inv() const { return s_isPrime ? inv_fermat() : inv_exgcd(); }
    inline m64 &operator=(const m64 &) = default;
    inline m64 &operator+=(const m64 &rhs) {
        v_ += rhs.v_ - s_mod;
        v_ += s_mod & -(v_ >> 127);
        return *this;
    }
    inline m64 &operator-=(const m64 &rhs) {
        v_ -= rhs.v_;
        v_ += s_mod & -(v_ >> 127);
        return *this;
    }
    inline m64 &operator*=(const m64 &rhs) {
        v_ = reduce(mul(v_, rhs.v_));
        return *this;
    }
    inline m64 &operator/=(const m64 &rhs) { return operator*=(rhs.inv()); }
    friend inline m64 operator+(const m64 &lhs, const m64 &rhs) { return m64(lhs) += rhs; }
    friend inline m64 operator-(const m64 &lhs, const m64 &rhs) { return m64(lhs) -= rhs; }
    friend inline m64 operator*(const m64 &lhs, const m64 &rhs) { return m64(lhs) *= rhs; }
    friend inline m64 operator/(const m64 &lhs, const m64 &rhs) { return m64(lhs) /= rhs; }
    friend inline bool operator==(const m64 &lhs, const m64 &rhs) { return lhs.v_ == rhs.v_; }
    friend inline bool operator!=(const m64 &lhs, const m64 &rhs) { return lhs.v_ != rhs.v_; }
    template <typename _Istream>
    friend inline _Istream &operator>>(_Istream &is, m64 &rhs) {
        i64 x;
        is >> x;
        rhs = m64(x);
        return is;
    }
    template <typename _Ostream>
    friend _Ostream &operator<<(_Ostream &os, const m64 &rhs) { return os << rhs.val(); }
    inline m64 pow(u64 y) const {
        m64 res(1), x(*this);
        for (; y != 0; y >>= 1, x *= x) if (y & 1) res *= x;
        return res;
    }
    static inline void set_mod(u64 mod, bool prime = true) {
    	s_mod = mod;
    	s_isPrime = prime;
    	r = get_r();
    	r2 = get_r2();
	}
private:
    static constexpr std::pair<u64, u64> mul(u64 x, u64 y) {
        u64 a = x >> 64, b = u32(x), c = y >> 64, d = u32(y), ad = a * d, bc = b * c;
        return {a * c + (ad >> 64) + (bc >> 64) + (((ad & ~UINT64_C(0)) + (bc & ~UINT64_C(0)) + (b * d >> 64)) >> 64), x * y};
    }
    static constexpr u64 mulh(u64 x, u64 y) {
        u64 a = x >> 64, b = u32(x), c = y >> 64, d = u32(y), ad = a * d, bc = b * c;
        return a * c + (ad >> 64) + (bc >> 64) + (((ad & ~UINT64_C(0)) + (bc & ~UINT64_C(0)) + (b * d >> 64)) >> 64);
    }
    static inline u64 get_r() {
        u64 two = 2, iv = s_mod * (two - s_mod * s_mod);
        iv *= two - s_mod * iv;
        iv *= two - s_mod * iv;
        iv *= two - s_mod * iv;
        iv *= two - s_mod * iv;
        return iv * (two - s_mod * iv);
    }
    static inline u64 get_r2() {
        u64 iv = -u64(s_mod) % s_mod;
        for (int i = 0; i != 128; ++i) ((iv <<= 1) >= s_mod) && (iv -= s_mod);
        return iv;
    }
    static constexpr u64 reduce(const std::pair<u64, u64> &x) {
        u64 res = x.first - mulh(x.second * r, s_mod);
        return res + (s_mod & -(res >> 127));
    }
    static constexpr u64 norm(i64 x) { return x + (s_mod & -(x < 0)); }
    u64 v_;
    static inline u64 s_mod = __mod;
    static inline u64 s_isPrime = __isprime;
    static inline u64 r = get_r();
    static inline u64 r2 = get_r2();
};
using mint = DynamicModInt<3>;
inline bool prime(__uint128_t x) {
    static constexpr __uint128_t first_prime[27] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103};
    if (x < 2) return false;
    std::vector<__uint128_t> bases;
    mint::set_mod(x);
    const mint one(1), none(-1);
#define DEFINE(threshold, cnt) if (x >= threshold) bases = std::vector<__uint128_t>(first_prime, first_prime + cnt)
    DEFINE(1543267864443420616877677640751301, 20);
    else DEFINE(564132928021909221014087501701, 18);
    else DEFINE(59276361075595573263446330101, 16);
    else DEFINE(6003094289670105800312596501, 15);
    else DEFINE(3317044064679887385961981, 14);
    else DEFINE(318665857834031151167461, 13);
    else DEFINE(3825123056546413051, 12);
    else DEFINE(341550071728321, 9);
    else DEFINE(3474749660383, 7);
    else DEFINE(2152302898747, 6);
    else DEFINE(4759123141, 5);
    else if (x >= 9006403) bases = {2, 7, 61};
    else if (x >= 489997) {
    	if ((not (x & 1) or not (x % 3) or not (x % 5) or not (x % 7) or not (x % 11) or not (x % 13) or not (
                  x % 17) or not (x % 19) or not (x % 23) or not (x % 29) or not (x % 31) or not (x % 37) or not (
                  x % 41) or not (x % 43) or not (x % 47) or not (x % 53) or not (x % 59) or not (x % 61) or not (
                  x % 67) or not (x % 71) or not (x % 73) or not (x % 79) or not (
                  x % 83)) and x % 89 and x % 97 and x % 101) return false;
    	__uint128_t hn = x >> 1;
    	mint p(mint(2).pow(hn));
    	if (p == one || p == none) {
    		p = mint(3).pow(hn);
    		if (p == one || p == none) {
    			p = mint(5).pow(hn);
    			return p == one || p == none;
    		}
    	}
    	return false;
    }
    else if (x >= 42799) {
    	if (!((x & 1) and x % 3 and x % 5 and x % 7 and x % 11 and x % 13 and x % 17 \
               and x % 19 and x % 23 and x % 29 and x % 31 and x % 37 and x % 41 and x % 43)) return false;
    	return mint(2).pow(x - 1) == one && mint(5).pow(x - 1) == one;
    }
    else if (x >= 841) {
    	if (not (((((not (x & 1) or not (x % 3) or not (x % 5) or not (x % 7) or not (x % 11) or not (
                x % 13) or not (
                x % 17)) or not (x % 19)) or not (x % 23) or not (x % 29) or not (x % 31) or not (x % 37) or not (
                x % 41) or not (x % 43) or not (
                x % 47)) or not (x % 53) or not (x % 59) or not (x % 61) or not (x % 67) or not (x % 71) or not (
                x % 73) or not (x % 79)) or not (x % 83) or not (x % 89) or not (x % 97) or not (x % 101) or not (
                x % 103))) return true;
    	return mint(2).pow(x - 1) != one;
    }
    else if (x >= 25) {
    	return not (not (x & 1) or not (x % 3) or not (x % 5) or not (x % 7) or not (
                x % 11)) and (x % 13) and (x % 17) and (x % 19) and (x % 23);
    }
    else if (x >= 4) return (x & 1) && (x % 3);
    for (int i = 0; i < 24; i++) {
    	if (x == first_prime[i]) return true;
    	if (x % first_prime[i] == 0) return false;
    }
#undef DEFINE
	__uint128_t y(x - 1);
    const unsigned iend = std::__countr_zero(y); // __builtin_ctzl
	y >>= iend;
    for (mint x : bases) {
    	mint z(x.pow(y));
    	if (z.val() == 1) continue;
    	unsigned i = 0;
    	for (; i ^ iend; i++) {
        	if (z == none) break;
        	z *= z;
    	}
    	if (i == iend) return false;
    }
    return true;
}
inline __int128 abs(__int128 x) { return x < 0 ? -x : x; }
inline __uint128_t rho(__uint128_t value) {
    if (value % 2 == 0) return 2;
    if (value % 3 == 0) return 3;
    if (value % 5 == 0) return 5;
    if (value % 7 == 0) return 7;
    static std::mt19937_64 rng;
    mint::set_mod(value);
    mint x, y, z, c, g;
    uint64_t i, j;
    while (true) {
        y = x = rng();
        z = 1;
        c = rng();
        i = 0;
        j = 1;
        while (++i) {
            x = x * x + c;
            z *= (x.val() > y.val()) ? (x - y) : (y - x);
            if (x == y || !z.val()) break;
            if (!(i % 127) || i == j) {
                g = std::__gcd(z.val(), value);
                if (g.val() > 1ull) return g.val();
                if (i == j) {
                    y = x;
                    j <<= 1;
                }
            }
        }
    }
}
inline auto crack(__uint128_t value) {
    struct _RetType { __uint128_t base; uint64_t power; };
    std::vector<_RetType> ret;
    if (prime(value)) {
        ret.push_back({value, 1ul});
        return ret;
    }
    _RetType node{2, 0};
    while (value % 2 == 0) ++(node.power), value >>= 1;
    if (node.power) ret.push_back(node);
    auto dfs = [&](auto self, __uint128_t v) {
        if (v <= 1) return;
        if (!prime(v)) {
            __uint128_t tmp = rho(v);
            self(self, tmp);
            self(self, v / tmp);
        }
        else {
            auto pos = std::find_if(ret.begin(), ret.end(), [=](const auto& x) { return x.base == v; });
            if (pos == ret.end()) ret.push_back({v, 1ul});
            else ++(pos->power);
        }
    };
    dfs(dfs, value);
    std::sort(ret.begin(), ret.end(), [=](const auto& x, const auto& y) { return x.base < y.base; });
    return ret;
}
inline __uint128_t readu128() {
    __uint128_t ret = 0;
    char c = getchar();
    while (!isdigit(c)) c = getchar();
    while (isdigit(c)) ret = ret * 10 + (c & 15), c = getchar();
    return ret;
}
inline void put128(__uint128_t x) {
    static char buf[32];
    static int curpos;
    curpos = 0;
    do {
        buf[curpos++] = x % 10;
        x /= 10;
    } while (x);
    while (curpos--) putchar(buf[curpos] | 48);
}
int main() {
    while (true) {
        __uint128_t x = readu128();
        if (!x) break;
        auto map = crack(x);
        for (auto [bs, pw] : map) put128(bs), printf("^%lu ", pw);
        putchar('\n');
    }
}