有 $n$ 颗宝石，第 $n$ 颗宝石的颜色为 ，其颜色在 $1\sim$ 之间。 你有一个法术。这个法术的执行机制如下：从 $n$ 颗宝石的 $2^n$ 个子集中等概率随机选择一个子集，设选出的集合为 ，满足 。随后从 个长度为 ，值域为 内的整数且值两两不同的 数列中等概率随机选择一个数列，设为 。最后对所有 ，将宝石 的颜色改为 。 你需要执行这个法术若干次，直到所有宝石的颜色相同。求期望次数，对 取模。 输入格式 第一行一个数 ，接下来一行 个数 。 输出格式 一行一个数，表示答案。 样例
3 1 2 3
样例输入 1
42
样例输出 1
5 1 1 2 2 2
样例输入 2
54346
样例输出 2
样例输入 3 5 1 2 3 3 3
输出3
54347
$n\le 5000$.