问题描述
现在要给n个小朋友发苹果，每一个小朋友都会有自己相应的苹果数目 ${A_1},{A_2},{A_3}, \cdots {A_n}$。 发苹果的时候，小朋友先从左到右随机站成一排。设站好后从左到右小朋友的标号是 ${p_1},{p_2},{p_3}, \cdots {p_n}$，他们所需要的苹果数目是 ${A_{{p_1}}},{A_{{p_2}}},{A_{{p_3}}}, \cdots {A_{{p_n}}}$，对于最左边的人要给他发 ${A_{{p_1}}}$个苹果，对于第i (i>1)个人，如果前面有一个人的苹果要求的数目比他多，那么就不用发给他苹果，否则发给他 ${A_{{p_i}}}$个苹果。那么对于某一个排列需要多少苹果就可以计算出来了。现在我们想知道对于所有的排列总共要发多少苹果。两个排列不一样当且仅当至少存在一个位置要求的苹果数目不一样。
输入描述
多组数据，第一输入数据组数T 。接下来每一组数据占两行。
第一行是一个n代表有n个小朋友。
第二行是n个整数${A_1},{A_2},{A_3}, \cdots {A_n}$ 代表n个小朋友要求的苹果数目以空格分开。
[参数说明]
所有输入均为整数
1<=T<=20
1<=n<=100000
1<=Ai<=1000000000
输出描述
对于每一组数据，输出答案占一行，输出格式为 Case #x: ans, x是数据编号从1开始，ans是答案对1000000007取余的结果。
输入样例
2
2
2 3
3
1 1 2
输出样例
Case #1: 8
Case #2: 9
提示：
对于第二组数据所有可能的苹果要求排列和其对应要发的苹果数目为
(1,1,2),4
(1,2,1),3
(2,1,1),2
所以最后答案为2+3+4=9
