Background

Special for beginners, ^_^

Description

某市位于一条数轴上，有n个点，从1到n，1是起点，n是终点。 当位于点x时： 有两种操作：

1. 走到点 $x+1$ 。
2. 如果地道起点位置 $x$ 没有打卡，打卡后使用 $x$ 点的单向地道，走到$a_x$处。

现在城管队员位于起点，想巡查所有n个点一次，问 $n$ 个点位的打卡顺序的不同排列有多少种？

答案对$10^9+7$取模。

Format

Input

每个测试点由多个测试例组成，单个文件不超过23MB。 每个测试例的第一行一个正整数 n $(\leq 10^6)$。 第二行包括n个整数，第i个数表示$a_i\ (1\leq a_i\leq i)$。保证$a_i$单调非递减。

Output

对每个测试例，输出一行包括一个整数，表示答案对$10^9+7$取模后的值。

Samples

3
1 1 2

4

Limitation

1s, 1024KiB for each test case.