Frederick 是一位年轻的程序员。他参加了所有能找到的编程竞赛,并且总是使用他最喜欢的编程语言 Fygon。不幸的是,即使他的算法在渐进意义上是最优的,他也经常收到“超出时间限制”(Time Limit Exceeded)的结果。这是因为 Fygon 解释器非常慢。尽管如此,Frederick 还是非常喜欢 Fygon,以至于他使用非渐进优化来使解决方案符合时间限制。为了简化这一过程,他请求你编写一个程序,能够估算他的 Fygon 程序执行的确切操作次数。
为简单起见,我们假设 Fygon 只有两条语句。第一条语句是 lag。它几乎可以替代任何其他语句。第二条语句是 for 循环:
for <variable> in range(<limit>):
<body>这意味着 <variable> 在 $0$ 到 <limit>$-1$ 的值之间迭代。在 Fygon 中,<variable> 是从 a 到 z 的小写字母,而 <limit> 要么是已经定义的 <variable>,要么是一个正整数常量。循环的 <body> 缩进四个空格,并且至少包含一条语句。
程序在变量 n 中接收输入。该变量具有特殊含义,不能用作循环变量。
你的任务是找到一个公式,根据变量 n 的值计算给定 Fygon 程序执行的 lag 操作次数。
输入格式
输入文件包含 Fygon 程序。没有两个循环使用相同的变量作为迭代器。在 range 中使用的每个变量要么是 n,要么是在某个外层循环中声明的。
该程序最多有 20 条语句,其中最多 6 条是循环。所有整数常量都在 1 到 9 之间。
输出格式
输出关于 n 的 lag 操作执行次数的公式。公式的长度应最多为 100 个字符(不包括空格)。公式应符合以下语法:
$\langle\text{Expression}\rangle ::= \langle\text{Product}\rangle \, ((\text{'+'} \mid \text{'-'}) \, \langle\text{Product}\rangle)^*$ $\langle\text{Product}\rangle ::= \langle\text{Value}\rangle \, (\text{'*'} \, \langle\text{Value}\rangle)^*$ $\langle\text{Value}\rangle ::= \text{'n'} \mid \langle\text{Number}\rangle \mid \text{'-'} \langle\text{Value}\rangle \mid \text{'('} \langle\text{Expression}\rangle \text{')'}$ $\langle\text{Number}\rangle ::= [\text{'0'}..\text{'9'}]^+ \, (\text{'/'} \, [\text{'0'}..\text{'9'}]^+)?$
样例
输入 1
for i in range(n):
for j in range(i):
lag
for x in range(5):
for y in range(n):
for z in range(n):
lag
lag输出 1
1/2 * n * (n-1) + 5 * (n*n + 1)