Problem : 205 - 妖怪之山

Problem Statistics

Solved Member: 23　　Submission: 70　　User Tried: 25

Statement:

幻想鄉的妖怪之山是萃香幾百年來的居處，
然而妖怪之山幅員廣大，
萃香又總是喝得爛醉，
所以當靈夢閒聊起妖怪之山的地形時，
萃香囧了。

唉唉，好險幾百年的記憶不是假的，
萃香還隱約記得每座山峰依序排列的高度，
不過既然說是隱約了，所以其中可能有一些假山出現，
然後她還記得妖怪之山最少是由3座山峰組成，
而且山峰一定是高低相間，
所以不會有長條順向坡道或是台地出現，
不過即使高度相同，每座山峰(不管它是真的還是假的)都是不一樣的。
那現在萃香把所有山峰的高度依序告訴學識淵博的帕秋莉，
請你幫助帕秋莉計算一下，
妖怪之山有幾種可能的樣子？

Input:Output:

第一行一個數字非負整數 n<=1500，
接著有 n 行，每行一個整數代表萃香所記得的山峰高度。
山峰高度也有可能是零或者是負的，但也算是一座山峰。

請輸出妖怪之山可能會有幾種排列方式，然後把那個數字 mod 12345 輸出就行了。

Sample Input:Sample Output:

5
1
0
2
3
0

HINT:

共有下列9種：

1	0	2
1	0		3
		2	3	0
	0		3	0
1			3	0
1	0		3	0
	0	2		0
1	0	2		0
1		2		0

Source:

98校內培訓

Problem Setter

lajisongyy_jack1

Testdata:

Test	Time	Memory	Score
0	1000ms	65536kb
1	1000ms	65536kb	20
2	1000ms	65536kb	20
3	1000ms	65536kb	20
4	1000ms	65536kb	20
5	1000ms	65536kb	20