JOKER1 - Knifes Are Fun

"Do you know, why I use a knife? Guns are too quick. You can't savor all the little emotions. You see, in their last moments, people show you who they really are. So in a way, I know your friends better than you ever did. Would you like to know which of them were cowards?"

Joker has many knifes, and he wants to assign a distinct integer to each knife so he can easily identify them. The i-th knife can have an integer between 1 and maxNumber[i], inclusive.

Return the number of ways he can assign numbers to his knifes, modulo 1,000,000,007. If it's impossible to assign distinct integers to the knifes, print 0.

Input

The first line contains the number of test cases T (1 <= T <= 666)

Each test case has 2 lines - 1st line denotes number of knifes N (1 <= N <= 66) Joker has and the 2nd line denotes the numbers {maxNumber[0]....maxNumber[N-1]} Joker has.

1 <= maxNumber[i] <= 3000

Output

Print the number of ways Joker can assign numbers to his knifes, modulo 1,000,000,007. If it's impossible to assign distinct integers to the knifes, print 0. In last line print the string "KILL BATMAN". Don't print any extra spaces.

Example

Input:
3
1
7
2
5 8
3
2 1 2

Output:
7
35
0
KILL BATMAN

Explanation

  • Test case 1 : Joker can assign any number between 1 and 7, inclusive, to the only knife.
  • Test case 2 : Joker wants you too think !
  • Test case 3 : (1,1,1) (1,1,2) (2,1,1) (2,1,2) are the possible combinations . As the numbering of knifes is not unique so the output is 0.

Added by:Rajarshi Sarkar
Date:2013-02-23
Time limit:0.5s
Source limit:5000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64

hide comments
2013-11-25 13:41:03 :-)
AC in python in 0.00sec
Nice problem
2013-11-25 13:41:03 Arika Saputro
easy one :D

Last edit: 2013-04-26 01:38:31
2013-11-25 13:41:03 Goldie
@Lakshman Thanks man for the test cases.
Really helped. had a stupid mistake.
2013-11-25 13:41:03 Narendra yadav
PL give here some tricky test case.
I m getting WA ,dont know why ? :(
2013-11-25 13:41:03 #vaidy_MIT#
Please don't forget to print KILL BATMAN and to take the modulo 1,000,000,007 ..dat costz me two wrong ans :( :)
2013-11-25 13:41:03 raunakrocks
ac on 1st attempt!! nyce prob.:D
2013-11-25 13:41:03 Buda IM (retired)
Test cases are faulty, I got assertion fail on maxNumber[i] < 2000

EDIT : No.Problem in your code my friend !
EDIT : My code actually only asserts correctness of your test data
EDIT : Thanks :)

Last edit: 2014-02-27 16:23:37
2013-11-25 13:41:03 Vipul Pandey
Easy one!
2013-11-25 13:41:03 [Lakshman]
got AC :) after 3 WA. Nice problem..But it will become easy if you read the problem carefully.

Last edit: 2013-02-28 23:16:29
2013-11-25 13:41:03 Problem Solver
ha-ha, read problem carefully :)
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.