该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

这是本题的困难版本，区别是数据范围。

注意，困难版本 并没有 在本场比赛中放出，后续的重现赛会加入，欢迎补题。

说明

国庆假期，小菜在教小学生们学习《组合数学》时发现这样一个问题：

我们通过简单的手算，可以很容易地在整式的乘法中，算出诸如 $(a+b)^1=a+b$，$(a+b)^2=a^2+2ab+b^2$ 等式子，但是他想如果要让小学生们求 $(a+b)^n$ 的展开式，就有点刁难小学生了。

于是他打算对小学生们好一点， 现在，他想刁难你用编程来求解这个问题，即给定一个 $n$，求 $(a+b)^n$ 的展开式。

为了方便小菜老师检查作业，请将输出格式统一为 (a+b)^n=*a^n+*a^(n-1)b+*a^(n-2)b^2+…+*b^n。

其中：“*”为系数，如果系数为 1，则需要省略系数；如果次数为 1，则需要省略次数；如果次数为 0，则需要省略；如果系数为 0，则需要省略这一项。

注意：前面 (a+b)^n 的次数是必有的，表达式的任何地方都不能有多余空格。

输入格式

输入一行一个整数$n$。

输出格式

输出一行一个完整的表达式。

样例

样例输入1

5

样例输出1

(a+b)^5=a^5+5a^4b+10a^3b^2+10a^2b^3+5ab^4+b^5

提示

$1 \leq n \leq 67$