记录编号	47409	评测结果	AAAAAAAAAA
题目名称	[扫地杯S3] 染色问题	最终得分	100
用户昵称	Truth.Cirno	是否通过	通过
代码语言	C++	运行时间	0.035 s
提交时间	2012-11-01 11:05:59	内存使用	2.83 MiB

#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;

struct bint
{
	int len,num[200];
};

bint bnum1;

bint bchange(long long num)
{
	bint a={0};
	if (!num)
	{
		a.len=1;
		return(a);
	}
	while (num)
	{
		a.num[a.len++]=num%10;
		num/=10;
	}
	return(a);
}

bool bcom(bint a,bint b)
{
	long long i;
	if (a.len>b.len)
	{
		return(0);
	}
	else if (a.len<b.len)
	{
		return(1);
	}
	else
	{
		for (i=a.len-1;i>=0;i--)
			if (a.num[i]>b.num[i])
			{
				return(0);
			}
			else if (a.num[i]<b.num[i])
			{
				return(1);
			}
	}
	return(0);
}

bint bsub(bint a,bint b)
{
	long long i;
	bool jie=0;
	for (i=0;i<a.len;i++)
	{
		a.num[i]=a.num[i]-b.num[i]-jie;
		if (a.num[i]<0)
		{
			a.num[i]+=10;
			jie=1;
		}
		else
			jie=0;
	}
	for (i=a.len-1;i>=0;i--)
		if (a.num[i]!=0)
		{
			a.len=i+1;
			break;
		}
	if (i==-1)
		a.len=1;
	return(a);
}

bint bmul(bint a,bint b)
{
	bint c={0};
	long long i,j,jin;
	c.len=a.len+b.len-1;
	for (i=0;i<a.len;i++)
		for (j=0;j<b.len;j++)
			c.num[i+j]+=a.num[i]*b.num[j];
	jin=0;
	for (i=0;i<=c.len;i++)
	{
		c.num[i]+=jin;
		jin=c.num[i]/10;
		c.num[i]%=10;
	}
	if (c.num[c.len])
	{
		c.len++;
	}
	return(c);
}

bint bmod(bint a,bint b)
{
	if (a.len==1&&a.num[0]==0)
	{
		bint c={0};
		c.len=1;
		return(c);
	}
	if (bcom(a,b)==1)
		return(a);
	long long i,len;
	len=a.len-b.len;
	for (i=b.len-1;i>=0;i--)
		b.num[i+len]=b.num[i];
	for (i=0;i<len;i++)
		b.num[i]=0;
	b.len=a.len;
	while (len!=-1)
	{
		while (bcom(a,b)==0)
			a=bsub(a,b);
		b.len--;
		len--;
		if (len!=-1)
			for (i=len;i<b.len;i++)
				b.num[i]=b.num[i+1];
		b.num[b.len]=0;
	}
	return(a);
}

bint bpower(bint num,long long level,bint moder)
{
	if (level==0)
		return(bnum1);
	bint temp;
	if (level&1)
	{
		temp=bpower(num,level>>1,moder);
		temp=bmod(bmul(temp,temp),moder);
		return(bmod(bmul(temp,num),moder));
	}
	else
	{
		temp=bpower(num,level>>1,moder);
		temp=bmod(bmul(temp,temp),moder);
		return(temp);
	}
}

void bprint(bint a)
{
	long long i;
	for (i=a.len-1;i>=0;i--)
		cout<<a.num[i];
}

int main(void)
{
	freopen("colora.in","r",stdin);
	freopen("colora.out","w",stdout);
	bnum1.len=1;
	bnum1.num[0]=1;
	long long n,m,p;
	bint bm,bp;
	cin>>n>>m>>p;
	bm=bchange(m);
	bp=bchange(p);
	if (n==1)
	{
		bprint(bmod(bm,bp));
		cout<<endl;
		return(0);
	}
	bprint(bmod(bmul(bm,bpower(bsub(bm,bnum1),n-1,bp)),bp));
	cout<<endl;
	return(0);
}