3410: 打工

魔王撒旦为了建立魔物的乐土，率领亚多拉玛雷克、艾谢尔、路西菲尔、以及马纳果达这四位恶魔大元帅进攻人类世界。然而此时手持圣剑的勇者艾米莉亚出现了。战败的魔王逃跑时穿越到了地球，以真奥贞夫的身份过着打工族的生活。

最近真奥贞夫手头有点紧，他接到一个待遇不错的任务，但是却没有时间。无奈之下，他只能找到可靠的YxuanwKeith来帮忙。

然而王导最近忙于筹拍宣传片，抽不出时间，于是 YxuanwKeith 又找到了你来替他完成这个工作。

YxuanwKeith帮忙的工作是为一个大赛设计分队方式。

这个比赛有N个人参加，我们可以给这N个人分任意数量（不超过N）的队伍，相同队伍的人用相同数字来表示。如果有多种表示，我们认为字典序最小的表示才是有效的。

例如

选手姓名 队伍

Jason       1

Dama       2

Ducky       2

SmallBell  3

 Awner     2

Tarjan       3

Jason 自己一队，Dama, Ducky, 和 Awner 一队， Tarjan 和 SmallBell 一队。

上述表示可以写为一个序列"1 2 2 3 2 3"，而且没有另一个等价序列是有效的。比如说序列"3 1 1 2 1 2"与当前分队方式等价，但由于不是字典序最小的表示，所以是无效的。

由于组队的情况实在是太多了，今年大赛组委会决定在比赛的第i天采用所有序列中字典序第i小的分队方式。

现在组委会会向你询问一个序列，希望你能告诉他们这个序列的分队方式会在哪一天被采用。由于答案可能会很大，所以组委会只关心对 1,000,007 取模之后的结果 

第一行，一个整数N表示参赛人数。

第二行，N个整数，表示询问的分队方式的序列。

1行，一个整数表示这种方式会在第几天被采用。答案对 1,000,007 取模。

3 
1 2 2

4