pollard-rho

/* pollard rho */


i128 In( string s){
    i128 x = 0;
    for(int i = 0;i<s.length();i++)x = x*10 + s[i] - 48;
    return x;
}

void out(i128 x){
    vi v;
    while(x){
        int y = x%10;
        x/=10;
        v.pb(y);
    }
    reverse(all(v));
    for(auto it : v)printf("%d",it);
}

i128 mul(i128 a,i128 b,i128 m){
    i128 ans = 0;
    while(b){
        ///cout<<a<<" "<<b<<" "<<m<<endl;
        if(b&1)ans = (ans + a)%m;
        a = (a+a)%m;
        b>>=1;
    }
    return ans;
}

i128 power(i128 base,i128 p,i128 m){
    ///cout<<base<<" "<<p<<" "<<m<<endl;
    if(p==0)return 1;
    if(p&1)return (base % m * power(base,p-1,m) % m)%m;
    else {
        i128 x = power(base,p/2,m)%m;
        return mul(x,x,m)%m;
    }

}


bool miller_rabin(i128 p,i128 d){

    i128 a = rand() %(p-4) + 2;
    i128 x = power(a,d,p);
    if(x==1||x==p-1)return true;
    while(d!=p-1){
        x = mul(x,x,p)%p;
        d = d*2;
        if(x==1)return false;
        if(x==p-1)return true;

    }
    return false;
}

bool isPrime(i128 n){
    if(n<=1||n==4)return false;
    if(n<=3)return true;
    i128 d = n-1;
    while(d%2==0){
        d/=2;
    }
    for(int i = 0;i<4;i++)if(!miller_rabin(n,d))return false;
    return true;
}

i128 GCD(i128 a,i128 b){
    if(b==0)return a;
    return GCD(b,a%b);
}

i128 pollard_rho(i128 n){
//  if(n%2==0)return 2;
//  if(n%3==0)return 3;
//  if(n%5==0)return 5;
    i128 x = 2,xs = 2,Count ,Size = 2,factor = 1;
    i128 c  = rand()%n+2;

    do {
        Count = Size;
        do{
            x = (mul(x,x,n) + c)%n;
            i128 ab;
            if(xs>x)ab = xs - x;
            else ab = x - xs;
            factor = GCD(ab,n);
        }while(Count--&&factor==1);
        Size*=2;
        xs = x;
    }while(factor==1);
    if(factor==n){
        do{
            xs = (mul(xs,xs,n) + c)%n;
            i128 ab;
            if(xs>x)ab = xs - x;
            else ab = x - xs;
            factor = GCD(ab,n);
        }while(factor==1);
    }
    return factor;

}

vector<i128>fact;

void FindFactors(i128 n){
    queue<i128>q;
    q.push(n);
    while(!q.empty()){
        i128 x = q.front();
        q.pop();
        i128 y = pollard_rho(x);
//      out(y);
//      out(x/y);
//      cout<<endl;
        if(isPrime(y))fact.pb(y);
        else{
            q.push(y);
        }
        if(isPrime(x/y))fact.pb(x/y);
        else {
            if(x/y!=1&&x/y!=x)q.push(x/y);
        }
    }
}



int main()
{
    //booster()
    ///read("input.txt");


    while(1){
        string s;
        char str[50];
        scanf("%s",str);
        s = str;
        fact.clear();
        if(s[0]=='0')return 0;
        i128 x = In(s);
        FindFactors(x);
        map<i128,int>m;
        for(auto it : fact)m[it]++;
//        for(auto it : fact){
//          out(it);
//          cout<<" ";
//        }
//        cout<<endl;
        for(auto it : m){
            out(it.ff);
            printf("^%d ",it.ss);
        }
        printf("\n");

    }

    return 0;
}