宝石装箱
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

颗宝石装进个箱子使得每个箱子中都有一颗宝石。第颗宝石不能装入第个箱子。求合法的装箱方案对取模。
两种装箱方案不同当且仅当两种方案中存在一颗编号相同的宝石装在不同编号的箱子中。

输入描述:

第一行一个整数。
第二行个整数。

输出描述:

输出一行一个整数表示答案。
示例1

输入

复制 
2
1 2

输出

复制 
1

说明

只有一种合法的装箱方案{2,1}。
示例2

输入

复制 
2
1 1

输出

复制 
0

说明

没有合法的方案。
示例3

输入

复制 
8
7 3 3 2 5 4 1 8

输出

复制 
14568

备注: