Background

屁股下藏雷!网友称办公座椅突然爆炸 击穿电脑机箱

2015年3月，厦门的刘小姐在家中上网，升降椅突然爆炸，产生的冲击力将椅子里的螺丝小垫片等零件从臀部射入她体内，插入刘小姐肛门的气压杆竟然有20多厘米长。

https://t10.baidu.com/it/fm=173&fmt=auto&h=220&img_JPG=&s=9113E137034274EEDA4C80C4030060B1&u=634813023%2C1382396758&w=311

Description

徐校长望着操场上成排的座椅，突然有了出题灵感。

如果把这些座椅排成一排，如果两个座椅的高度相同，那么可以把两个座椅之间的所有座椅 的高度都调节成和两端相同。这种操作可以实施任意次。

问最终不同的座椅布局有多少种（mod 1e9+7）?

输入格式

输入以如下格式从标准输入读入。

$N$ $C_1$ $C_2$ $\cdots$ $C_N$

输出格式

输出最终可能得到的座椅布局的总数，对 $10^9+7$ 取模。

输入输出样例 #1

输入 #1

5
1 2 1 2 2

输出 #1

3

Limitation

1s, 1024KiB for each test case.

说明/提示

限制条件

• $1 \leq N \leq 2 \times 10^5$
• $1 \leq C_i \leq 2 \times 10^5\ (1 \leq i \leq N)$
• 输入均为整数