给定多项式f(x)=anxn+an-1xn-1+…+a0x0，如果an≠0，我们称f(x)是一个n次多项式。
类似自然数里的“质数”的概念，也可以给出“质多项式”的概念。给定多项式f(x)，如果找不到次数至少为1的多项式g(x)和h(x)满足f(x)=g(x)*h(x)，我们称f(x)是质多项式。
为了简化起见，我们规定多项式各项的系数只能取两个数：0或1。并且重新定义在[0，1]上的加法和乘法如下：
0+0=0 0+1=1 1+0=1 1+1=0
0*0=0 0*1=0 1*0=0 1*1=1
下面给出一个多项式相乘的例子：
  (x2+x1)*(x1+1)=x3+x2+x2+x1=x3+x1
编写程序，求次数为k的质多项式。

输入
输入由若干行组成。每行只有一个整数k（k<=30），整个输入由k=0结束。K=0这一行不需要处理。

输出
对每个输入行，输出质多项式akxk+ak-1xk-1+…+a0x0，满足ak2k+ak-12k-1+…a020的值最小。

测试用例输入
1
2
5
0
测试用例输出
x
x^2+x+1
x^5+x^2+1

＃i nclude <iostream>
＃i nclude <cmath>

using namespace std;

unsigned long len(unsigned long x)
{
 unsigned long count = 0;

 while (x!=0)
 {
  count++;
  x = x>>1;
 }
 return count;
}

int main()
{

 unsigned long k;

 cin >> k;

 while ( k != 0 )
 {
  if ( k == 1 )
   cout << 'x' <<endl;
  else
  {

   unsigned long A = 1 << k;
   
   A++;

   bool flag = true;
   while ( flag == true )
   {
    A+=2;

    
    flag = false;

    for ( int B  = 2 ; B < sqrt(A)*2 ; B++ )
    {
     unsigned long tempA = A;
     unsigned long tempB = B;
   //  cout << B << endl;
     while ( tempA >= tempB )
     {
      unsigned long tempB = B;

      tempB = tempB << ( len(tempA) - len(tempB) );
      tempA ^= tempB;
      
     

   //   cout << endl;
     }

     if (tempA == 0 )
     {
      flag = true;
      break;
     }

    }
   }

   for ( int i = len(A)-1 ; i > 0 ; i-- )
    if ( A & 1<<(i) ) cout << "x^" << i << '+';
   cout << 1 <<endl;
  }

  cin >> k;
 }

                                                                                        
 return 0;
}