DZY有一个$n\times n$的方阵，方阵是用来膜拜吉丽的。每天早上，DZY都会找来$n^2$个身高互不相同的人（从矮到高编号为$1,2,\cdots,n^2$），让他们排列成$n \times n$的方阵。 当大家开始Orz吉丽时，吉丽会微笑着向大家挥手致意。不过吉丽有一个小要求，他希望沿着方阵的第$i$列看去能看到$a_i$个人（高的人会挡住其后方比他矮的人）。 现在，吉丽想知道有多少种排列方式能满足他的要求，他要DZY赶紧把它算出来。 现在，DZY让你赶紧把它算出来。
输入有多组测试数据。($TestCase\leq 5$) 第一行，一个整数$n(1\leq n\leq 10^5)$. 第二行，$n$个正整数$a_i(1\leq a_i\leq n)$。
对于每组测试数据，输出一个答案，表示满足条件的方案数。 由于答案过大，吉丽希望你告诉他答案对$10^9-51711$取模的结果。
2 1 2 3 2 1 1 7 2 4 3 5 2 4 3
6 20160 67779489
询问 1. 有6种不同的方式如图所示.
