你的朋友达尔文是一位非常著名的博物学家，他告诉你，他目前正在尝试统计他两年前发现的一种非常特殊的树木的品种数量。

他告诉你这些树非常奇特。首先，它们是扁平的：它们的一侧朝南，另一侧朝北。其次，当它们的分支分叉时，会精确地分成两个子分支，分别指向两个相反的方向：一个指向西，另一个指向东。总而言之，这样的树可以很容易地表示为计算机科学家所熟悉的二叉树。（在数学上，二叉树要么是空树，要么是一个内部节点，它恰好有两个子节点，这两个子节点本身也是二叉树。）

作为一名优秀的程序员，你一听到二叉树就感到兴奋。达尔文继续解释道：在这种树中，分支要么是水平的，要么是向上的。你仍然沉迷于二叉树，你发现这相当于说，在二叉树表示中，如果内部节点用分支分叉处的海拔高度（距离地面的距离）来标记，那么非根节点的标签总是大于或等于其父节点的标签。空树没有标签。

虽然你觉得这个性质相当枯燥且没什么意思，但达尔文接着告诉你一个他最近发现的关于他最喜欢的树种的非常令人惊讶且微妙的事实。在与达尔文进行了长时间的讨论后，你终于明白这个性质可以用二叉树表示法简单地表达出来。即：如果对该物种的任何一棵树的标记二叉树进行中序遍历，所得的海拔序列总是相同的！（空树的中序遍历是空序列；如果树非空，其中序遍历是左子树的中序遍历、根节点标签、右子树的中序遍历的连接。）

在听完你朋友令人印象深刻的研究成果后，你催促他详细说明他用来统计这种特别令人惊讶的物种的品种的方法。这促使他透露了他目前正在研究的假设：给定品种的每一棵树都由同一棵二叉树表示，该二叉树唯一地标识了该品种。此外，每一棵满足上述条件的标记二叉树确实对应于一个现有的品种。达尔文相信某种数学工具可以用来统计这些品种，但他没有足够的数学背景来做到这一点。

现在你对达尔文的工作印象深刻，轮到你了：通过编写一个程序来统计该物种的品种数量，让他也对你刮目相看。

输入格式

输入包含以下行： 第一行：该物种任何一棵树的中序遍历所产生的海拔序列的元素个数 $N$； 接下来的 $N$ 行表示海拔序列（单位为毫米），每行一个整数。

数据范围

$N$ 和海拔高度均大于或等于 $0$ 且小于或等于 $1\,000\,000$。

输出格式

输出一行，包含一个整数，即该物种树木的品种数量，对 $1\,000\,000\,007$ 取模。

样例

样例输入 1

6
3
1
6
2
4
5

样例输出 1

1

样例输入 2

6
1
1
1
1
1
1

样例输出 2

132