小明最近在研究一个问题：

在整式的乘法中，(a+b)^1=a+b(a+b)1=a+b，(a+b)^2=a^2+2ab+b^2(a+b)2=a2+2ab+b2，这些都很容易计算。 但是我们如果要求的(a+b)^n(a+b)n展开式， 就不太容易了。

小明想请你帮他解决这个问题

输入格式

输入仅一行，一个整数 nn。

输出格式

输出一行表达式，格式为：(a+b)^n=?a^n+?a^(n-1)b+?a^(n-2)b^2+…+?b^n

其中?为系数。

注意，对于每一项：

• 如果系数为 11，则需要省略系数；
• 如果次数为 00，则需要省略这一项；
• 如果系数为 00，则需要省略这一项。

注意：前面(a+b)^n的次数 nn 是必有的。

数据范围

对于 30\%30% 的数据，n \leq 15n≤15

对于 60\%60% 的数据，n \leq 30n≤30

对于 100\%100% 的数据，n \leq 60n≤60

Sample Input

4

Sample Output

(a+b)^4=a^4+4a^3b+6a^2b^2+4ab^3+b^4

其实就是杨辉三角

#include <iostream>
using namespace std;
int main()
{
	long long s[100][100], n,i,j;
	s[0][0]=1;
	s[1][0]=s[1][1]=1;
	cin>>n;
	for (i=2;i<=n;i++)
	{
		s[i][0]=s[i][i]=1;
		for (j=1;j<=i-1;j++)
		{
			s[i][j]=s[i-1][j]+s[i-1][j-1];
		}
	}
	cout<<"(a+b)^"<<n<<"=";
	if (n==1) cout<<"a+b";
	else if (n==0) cout<<"1";
	else {
		cout<<"a^"<<n;
		for (j=1;j<i-1;j++)
		{  
			if (j!=1&&n-j!=1) cout<<"+"<<s[n][j]<<"a^"<<n-j<<"b^"<<j;
			else if (j==1&&n-j!=1) cout<<"+"<<s[n][j]<<"a^"<<n-j<<"b";
			else if (j!=1&&n-j==1) cout<<"+"<<s[n][j]<<"a"<<"b^"<<j;
			else if (j==1&&n-j==1) cout<<"+"<<s[n][j]<<"a"<<"b";
		}
		cout<<"+b^"<<n;
	}	
}