时间限制：1秒　　内存限制：256M

---

【问题描述】

　　小L热衷于游戏卡片之下，在游戏中，有从左到右排成一排的四个格子。每个格子要么是空的，要么住着一只Bigbob。每个Bigbob有一个不超过 \(k\) 的血量；血量减到 0 视为死亡。那个格子随即空出。
　　当一只Bigbob受到伤害后，假如它没有死亡且剩余血量为 \(t\)，它会从左数第一个空格处召唤一只血量为 \(a[t]\) 的Bigbob；若没有空格，则不会召唤。
　　法术R定义为：从左往右，对每个Bigbob造成一点伤害；假如有Bigbob死亡，重复上述效果。
　　聪明的小L发现，在某些情况下，当他发动法术R时，游戏会陷入循环。
　　他想求出这样的初始情形有多少种。

【输入格式】

　　输入一个正整数 \(k\)，表示Bigbob的满血量； 随后一行 \(k-1\) 个正整数，表示 \(a[1]~a[k-1]\)。

【输出格式】

　　输出一个整数，表示答案。

【输入输出样例】

　Input

2 
2

　Output

31

【输入输出样例说明】

　　Bigbob最多有2血，满血Bigbob受伤会召出新的。 循环的初始状态有：
　　　　(2,1,0,0),(1,2,0,0),(2,0,1,0),(2,1,1,0),(0,2,1,0),(1,2,1,0),
　　　　(2,2,1,0),(1,0,2,0),(0,1,2,0),(1,1,2,0),(2,1,2,0),(2,1,0,1),
　　　　(0,2,0,1),(1,2,0,1),(0,2,1,1),(1,2,1,1),(0,0,2,1),(1,0,2,1),
　　　　(0,1,2,1),(1,1,2,1),(2,1,2,1),(0,2,2,1),(1,2,2,1),(2,1,0,2),
　　　　(1,2,0,2),(2,0,1,2),(2,1,1,2),(0,2,1,2),(1,2,1,2),(2,2,1,2),
　　　　(2,1,2,2)

【数据说明】

　　对于 \(30\%\) 的数据，\(k ≤ 5\)
　　对于 \(70\%\) 的数据，\(k ≤ 10\)，\(a[i]=k\)
　　对于 \(100\%\) 的数据，\(k ≤ 15\)，\(1≤a[i]≤k\)

【来源】

　　Mr.he