You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

$a_1,a_2,...,a_{n*(n+1)/2}$ 为一个超级排列，当且仅当它可以划分成 $n$ 个连续的长度不一样的排列。

如 [1,1,2,1,2,3,1,2,3,4]是一个超级排列， 可以划分成 1 | 12| 123 | 1234。

如[2,1,3,1,2,1] 是一个超级排列， 可以划分成 21| 312| 1；也可以划分成213|1|21；还可以划分成 213|12|1等等。

给你一个长度为 $n(n+1)/2$ 的超级排列，问有多少种不同的划分方式，使得划分成 $n$ 个长度不一样的连续的排列。输出答案%(1e9+7)。

输入格式

第一行一个整数 $n$。 第二行 n(n+1)/2 个数，保证这是一个超级排列。

输出格式

一个整数。

3
1 2 1 3 2 1

4

数据范围

子任务1 (10分): n≤6

子任务2 (10分): n≤10

子任务3 (20分): n≤20

子任务4 (20分): n≤50

子任务5 (20分): n≤100

子任务6 (20分): n≤500