P15193 [SWERC 2019] Counting Trees

你的朋友达尔文是一位非常著名的自然学家，他告诉你他目前正试图计算一种他两年前发现的特殊树木的变种数量。 他告诉你这些树非常奇特。首先，它们是扁平的：它们的一侧朝南，另一侧朝北。其次，当它们的一个分支分裂时，它总是恰好分裂成两个子分支，这两个子分支朝向两个相反的方向：一个向西，另一个向东。总而言之，这种树可以非常容易地表示为一棵二叉树，就像计算机科学家所熟悉的那样。（从数学上讲，二叉树要么是空树，要么是一个内部节点，该节点恰好有两个孩子，这两个孩子本身也是二叉树。） 作为一名优秀的程序员，你一听到二叉树就兴奋起来。达尔文继续解释：在这样的树中，分支要么是水平的，要么向上生长。你仍然痴迷于二叉树，并意识到这对应于在二叉树表示中，如果内部节点用对应分支分裂的高度（离地面的距离）来标记，那么非根节点的标签总是大于或等于其父节点的标签。空树没有标签。 当你觉得这个属性相当无聊且不太有趣时，达尔文继续告诉你他最近发现的关于他最喜欢的树种的真正惊人且微妙的事实。在与达尔文进行了长时间的讨论后，你终于理解了这个属性可以简单地用二叉树表示来表达。即，如果对该物种任何树的标记二叉树进行中序遍历，所得的高度序列总是相同的！（空树的中序遍历是空序列；如果树非空，其中序遍历是左子树的中序遍历序列，后跟根节点的标签，再跟右子树的中序遍历序列。） 在听完了你朋友令人印象深刻的研究成果后，你催促他详细说明他用来计算这种特别令人惊讶的物种的变种数量的方法。这使他揭示了他目前正在研究的假设：给定变种的每棵树都由同一棵二叉树表示，该二叉树唯一标识该变种。此外，每个满足上述条件的标记二叉树确实对应一个存在的变种。达尔文相信某种数学工具可以用来计算变种数量，但他没有足够的数学背景来实现。 既然你对达尔文的工作印象深刻，现在轮到你了：通过编写一个计算该物种变种数量的程序来给他留下深刻印象。

输入包含以下行： - 第一行：任何树的中序遍历所产生的高度序列的元素数量 $N$； - 接下来的 $N$ 行表示高度序列，单位为毫米，每行一个整数。

一行一个整数，表示该物种的树木变种数量，对 $1\,000\,000\,007$ 取模。

#### 数据范围 $N$ 和高度均大于等于 $0$ 且小于等于 $1\,000\,000$。 翻译由 DeepSeek 完成