等价交换

Time Limit: 1000MS

Memory Limit: 65536K

Description

“想要得到一样东西,必须付出与之相等的代价,这就是炼金术的基本原则——等价交换,那时我们相信,这就是这个世界的真理”
在n个数字里(a1,a2...an,0<=ai<=9),你可以在数字之间添加+号,或者=号使得表达式成立。
例如 1 1 1 1 可以变成 1 + 1 = 1 + 1 , 1 = 1 = 1 = 1  11 = 11 均使得表达成立(至少有一个"=")。

Input

第一行输入一个整数n(2=<n<10),接着输入n个数。
当n = 0时结束

Output

输出最多有几种方式使得表达式成立。

Sample Input

4
1 1 1 1
5
1 2 3 4 5

Sample Output

3
1

Hint

Source

Dash

提交代码