小明旅游回来了，他发现自己旅游花了好多钱，所以他打算去打工挣钱。他找到了一份图书馆的工作，每天要把读者还回来整整齐齐的排列好。他觉得这份工作有些无聊，所以他想将这些图书按照他希望的顺序排列。

今天有n本图书归还了，小明想将这些图书从左到右排列好。他对于每一本书都会给一个“希望值”a[i]，这表示，如果从左往右数，这本书如果放在第k个位置上，那k必须满足k<=a[i]。但是小明发现，排列这些书本有很多的方案数，他数不过来，所以他想让你写一个程序帮他计算有几种方案，由于答案可能很大，所以你告诉他答案关于10007取模后的数字就好。

第一行：一个正整数n

一个正整数，表示排列方案数量对于10007的取模。如果小明没有办法按照这些希望值排列书本，则输出-1。

第1本书与第2本书必须放置在左边两个位置上，剩下的第三个位置放置第三本书。放置方案为（1,2,3）和（2,1,3），共2种。

对于20%的数据，n≤20，1<=a[i]<=20

对于40%的数据，n≤50, 1<=a[i]<=100

对于60%的数据，n≤500, 1<=a[i]<=1000

对于100%的数据，n≤1000, 1<=a[i]<=2000