> /*--------------------------------------------------------------------------------------------*\
> *		
> *		       
> *		
> \*--------------------------------------------------------------------------------------------*/
> 
> #include <iostream.h>
> 
> class Length							//本类只适合做此题，还不能当作整数应用，除非完善该类的各种功能
> {
> private :
> 	long * data;
> 	int length;
> 	int current;
> 	
> 	void Enlarge()
> 	{
> 		long *In=new long[2*length];
> 		for(int i=0;i<length;i++)
> 		{
> 			In[i]=data[i];
> 		}
> 		delete data;
> 		data=new long(2*length);
> 		for(int j=0;j<length;j++)
> 		{
> 			data[i]=In[i];
> 		}
> 		length*=2;
> 		delete In;
> 	}
> 
> public:
> 
> 	Length(int n)
> 	{
> 		data=new long[50];
> 		for(int x=0;x<50;x++)
> 		{
> 			data[x]=0;
> 		}
> 
> 		length=50;
> 
> 		int sum=0;
> 		int i=0;
> 		do 
> 		{
> 			data[i]+=n;
> 			n=data[i]/10000;
> 			data[i]%=10000;
> 			i++;
> 		}while(n!=0);
> 
> 	}
> 	
> 	Length(Length & L)
> 	{
> 		this->length=L.length;
> 		data=new long[L.length];
> 		for(int i=0;i<L.length;i++)
> 		{
> 			data[i]=L.data[i];
> 		}
> 	}
> 
> 	Length()
> 	{
> 		data=new long[50];
> 		for(int i=0;i<50;i++)
> 			data[i]=0;
> 	}
> 
> 	~Length()
> 	{
> 		if(length!=0)
> 		{
> 			length=0;
> 			delete data;
> 		}
> 	}
> 
> 	void operator +=(int i)
> 	{
> 		int sum=0;
> 
> 		data[0]+=i;
> 		sum=data[0]/10000;
> 		data[0]%=10000;
> 
> 		int j=0;
> 		for(j=1;j<length&&sum!=0;j++)
> 		{
> 			data[j]+=sum;
> 			sum=data[j]/10000;
> 			data[j]%=10000;
> 		}
> 
> 		if(j==length&&sum!=0)
> 		{
> 			int temp=length;
> 			Enlarge();
> 			for(j=temp;j<length&&sum!=0;j++)
> 			{
> 				data[j]=sum;
> 				sum=data[j]/10000;
> 				data[j]%=10000;
> 			}
> 		}
> 	}
> 	
> 	Length & operator +=(const Length &L)
> 	{
> 
> 		int temp=0;
> 		int k=0;
> 		
> 		if(this==&L)
> 		{
> 			(*this)*=2;
> 			return * this;
> 		}
> 
> 		for(int i=0;i<L.length;i++)
> 		{
> 			data[i]+=L.data[i];
> 			temp=data[i]/10000;
> 			data[i]%=10000;
> 
> 			for(k=i+1;temp!=0&&k<length;k++)
> 			{
> 				data[k]+=temp;
> 				temp=data[k]/10000;
> 				data[k]%=10000;
> 			}
> 			if(k==length&&temp!=0)
> 			{
> 				int sum=length;
> 				Enlarge();
> 				for(k=sum;k<length&&sum!=0;k++)
> 				{
> 					data[k]+=temp;
> 					temp=data[k]/10000;
> 					data[k]%=10000;					
> 				}
> 			}
> 
> 		}
> 		return * this;
> 	}
> 	
> 	Length & operator *=(const Length & L)
> 	{
> 		int temp=0;
> 		int i=0;
> 		long * ch=new long[length];
> 		
> 		for(int x=0;x<length;x++)
> 			ch[x]=0;
> 
> 		for(int m=0;m<length;m++)
> 		{
> 			temp=0;
> 			for(i=0;i<length-m;i++)
> 			{
> 				ch[i+m]+=temp;
> 				ch[i+m]+=data[i]*L.data[m];
> 				temp=ch[i+m]/10000;
> 				ch[i+m]%=10000;
> 			}
> 
> 		}
> 
> 		for(int a=0;a<length;a++)
> 		{
> 			data[a]=ch[a];
> 		}
> 
> 		delete ch;
> 		return * this;
> 	}
> 
> 	Length & operator *=(int value)
> 	{
> 
> 		int sum=0;
> 		int temp=0;
> 		int i=0;
> 		long * ch=new long[length];
> 		
> 		for(int x=0;x<length;x++)
> 			ch[x]=0;
> 
> 		for(int m=0;m<length&&value!=0;m++)
> 		{
> 			temp=0;
> 			sum=value/10000;
> 			value%=10000;
> 			
> 			for(i=0;i<length-m;i++)
> 			{
> 				ch[i+m]+=temp;
> 				ch[i+m]+=data[i]*value;
> 				temp=ch[i+m]/10000;
> 				ch[i+m]%=10000;
> 			}
> 
> 			value=sum;
> 		}
> 
> 		for(int a=0;a<length;a++)
> 		{
> //			cout<<endl<<"ch["<<a<<"]:"<<ch[a]<<endl;
> 			data[a]=ch[a];
> 		}
> 		delete ch;
> 		return * this;
> 	}
> 	
> 	Length & operator -=(int i)
> 	{
> 		int sum=0;
> 
> 		for(int j=0;i!=0&&j<length;j++)
> 		{
> 			sum=i/10000;
> 				i%=10000;
> 			data[j]-=i;
> 
> 			i=sum;
> 			if(data[j]<0)
> 			{
> 				data[j]+=10000;
> 				i+=1;
> 			}
> 		}
> 		return * this;
> 	}
> 
> 	Length & operator -=(Length & L)
> 	{
> 		int sum=0;
> 		int j=0;
> //		if((*this)>L)				//with the note below,in order to get the
> 									//minus value when a small integer number substract a bigger one;
> 		for(j=0;j<length;j++)
> 		{
> 
> 			L.data[j]+=sum;
> 			data[j]-=L.data[j];
> 
> 			sum=0;
> 			if(data[j]<0)
> 			{
> 				data[j]+=10000;
> 				sum+=1;
> 			}
> 		}
> /*		else
> 		{
> 			for(j=0;j<length;j++)
> 			{
> 				data[j]+=sum;
> 				data[j]=L.data[j]-data[j];
> 				
> 				sum=0;
> 				if(data[j]<0)
> 				{
> 					data[j]<10000;
> 					sum+=1;
> 				}
> 			}
> 			for(j=length-1;j>=0;j++)
> 			{
> 
> 				if(data[j]!=0)
> 				{
> 					data[j]=0-data[j];
> 					break;
> 				}
> 			}
> 		}
> */
> 		return * this;
> 	}
> 
> 	Length& operator =(Length &L)
> 	{
> 		if(this==&L)
> 			return *this;
> 
> 		this.~Length();
> 		length=L.length;
> 		data=new long[length];
> 		for(int i=0;i<length;i++)
> 		{
> 			data[i]=L.data[i];
> 		}
> 		return * this;
> 	}
> 	
> 	int operator ==(Length & L)
> 	{
> 		if(L.length!=length)
> 			return 0;
> 
> 		int i=0;
> 		for(i=0;i<length;i++)
> 		{
> 			if(data[i]!=L.data[i])
> 				break;
> 		}
> 		if(i==length)
> 		return 1;
> 		else
> 		return 0;
> 	}
> 	int operator >(Length & L)
> 	{
> 
> 		int i=0;
> 		 for(i=L.length-1;i>=0;i++)
> 		 {
> 			if((data[i]!=0||L.data[i]!=0)&&data[i]!=L.data[i])
> 				break;
> 		 }
> 
> 		 if(i==-1)
> 			 return -1;
> 		 if(data[i]>L.data[i])
> 			 return 1;
> 		 else if(data[i]<=L.data[i])
> 			 return 0;
> 		 else
> 			 return -1;
> 	}
> 
> //-------------------------------------------output the value of the object of Length
> 	void print()
> 	{
> 		int first=0;
> 		int sum=0;
> 		for(int i=length-1;i>=0;i--)
> 		{
> 			sum=data[i];
> 
> 			if(i==0&&first==0)
> 			{
> 				cout<<sum;
> 				break;
> 			}
> 			if(sum==0&&first==0)
> 				continue;
> 			if(sum!=0&&first==0)
> 			{
> 				cout<<sum;
> 				first=1;
> 				continue;
> 			}
> 			if(sum==0&&first!=0)
> 			{
> 				cout<<"0000";
> 				continue;
> 			}
> 			if(sum!=0&&first!=0)
> 			{
> 
> 				if(sum>=1000)
> 					;
> 				else if(sum>=100)
> 					cout<<"0";
> 				else if(sum>=10)
> 					cout<<"00";
> 				else if(sum>=0)
> 					cout<<"000";
> 
> 				cout<<sum;
> 				continue;
> 			}
> 
> 		}
> 	}
> };
> class Insect
> {
> 	Length *amount;
> 	int M,N;
> public:
> 	Insect(int n=0,int m=0)
> 	{
> 		M=m;
> 		N=n;
> 		if(m!=0&&n!=0)
> 		get_Num();
> 	}
> 	~Insect()
> 	{
> 		if(M!=0&&N!=0)
> 			delete amount;
> 	}
> 	
> 	friend istream & operator >>(istream & i,Insect &L);
> 
> 	void get_Num()
> 	{
> 		amount=new Length(1);
> 		if(N==1)
> 			return;
> 
> 		int temp=0;
> 		for(int i=0;i<N;i++)
> 		{
> 			(*amount)*=M;
> 		}
> 
> //------------------------------------below are tow different cases
> 		if(M%2!=0)
> 		{
> 			(*amount)-=1;
> 		}
> 		else
> 		{
> 
> 			Length L(1);
> 			temp=M/2;
> 			for(int x=0;x<N;x++)
> 				L*=temp;
> 
> 			(*amount)-=L;
> 		}
> 
> 
> 	}
> 
> //--------------------------------output the number of different combinations
> 	void print()
> 	{
> 		if(M!=0&&N!=0)
> 		amount->print();
> 		else
> 			cout<<"还没有输入值!"<<endl;
> 	}
> 
> };
> 
> ostream & operator <<(ostream & s,Insect & L)
> {
> 	L.print();
> 	return s;
> }
> 
> istream & operator >>(istream & i,Insect &L)
> {
> 	cin>>L.N;
> 	cin>>L.M;
> 	while(L.N!=0||L.M!=0)
> 	{
> 		if(L.N<1||L.N>15||L.M>100000000||L.M<1||L.N>L.M)
> 		{
> 			cout<<"确定输入的N和M分别位于[1,15]和(N,100000000]! 输入0，0则退出:"<<endl;
> 			cin>>L.N;
> 			cin>>L.M;
> 			continue;
> 		}
> 		
> 		if(L.M!=0&&L.N!=0)
> 		{
> 
> 			L.get_Num();
> 			break;
> 		}
> 	}
> 	return i;
> }
> 
> void main()
> {
> 	Length amount(1);
> 	amount.print();
> 	cout<<endl;
> 	Insect insect;
> 	cout<<"输入两个数n,m,分别介于[1,15]和[n,100000000]:"<<endl;
> 	cin>>insect;
> 	cout<<endl<<"可以到达的组合数是:"<<endl<<insect<<endl;
> 
> }