Permutation with requirement of costs

permutation_with_conds.py

import fileinput

inputs = fileinput.input()
input_vals = []

for n in inputs:
	input_vals.append(n.replace('\n', ''))

numTestCases = int(input_vals[0])


def count_possibilities(costs):
	# global count_possibilities
	if len(costs) == 1:
		if costs[0] == 0:
			return 1
		else:
			return 0

	countPossibilities = 0
	for j in range(len(costs)):
		if costs[j] == 0:
			newcosts = [max(i-1, 0) for i in costs]
			newcosts = newcosts[:j] + newcosts[j+1:]
			countPossibilities += count_possibilities(newcosts)
	return countPossibilities % (10 ** 9 + 7)

def count_possibilities2(costs):
	# countCostsLessThan = []
	countPossibilities = 1 
	possibilities = []
	for i in range(len(costs)):
		possibilities.append(len([c for c in costs if c <= i]) - i)
		if possibilities[i] <= 0:
			return 0

	for i in range(len(costs)):
		countPossibilities = countPossibilities * possibilities[i]
		countPossibilities = countPossibilities % (10 ** 9 + 7)
	return countPossibilities

# def count_possibilities3(costs):

# 	countPossibilities = 1 
# 	sorted_costs = sorted(costs)
# 	costs_dist = {}
# 	curr_cost = 0
# 	i = 0 
# 	costs_dist[0] = 0
# 	while curr_cost < len(costs):

# 		if i == len(costs):
# 			for t in range(curr_cost + 1, len(costs)):
# 				costs_dist[t] = costs_dist[curr_cost]
# 			break

# 		if sorted_costs[i] <= curr_cost:
# 			costs_dist[curr_cost] += + 1

# 		else:
# 			prev_cost_dist = costs_dist[curr_cost]
# 			curr_cost += 1
# 			costs_dist[curr_cost] = prev_cost_dist
# 			if sorted_costs[i] == curr_cost:
# 				costs_dist[curr_cost] += 1
# 		i += 1

# 	for i in range(len(costs)):

# 		possibilities = (costs_dist[i] - i)
# 		if possibilities <= 0:
# 			return 0
# 		countPossibilities = countPossibilities * possibilities
# 		countPossibilities = countPossibilities % (10 ** 9 + 7)
# 	return countPossibilities

for i in range(numTestCases):
	N = int(input_vals[2*i + 1])
	costs = [int(c) for c in input_vals[2*i+2].split(' ')]
	print count_possibilities2(costs)


"""
Example Solution:

# Enter your code here. Read input from STDIN. Print output to STDOUT
import sys

T = int(sys.stdin.readline())
MOD = 1000000007

for t in xrange(T):
    n = int(sys.stdin.readline())
    c = sorted(map(int, sys.stdin.readline().split()))
    ret = 1
    if c[0] != 0:
        print 0
    else:
        for i in xrange(1, n):
            cnt = i-(c[i]-1)
            if cnt <= 0:
                ret = 0
                break
            ret = (ret * cnt) % MOD
        print ret

Example Testcase:
5
17
3 3 6 1 3 9 4 2 13 5 5 1 3 11 2 1 0
18
2 1 9 0 5 8 1 4 1 1 2 0 0 10 2 5 1 5
18
2 9 3 2 5 2 1 0 11 2 1 7 0 8 6 2 0 4
18
6 1 0 2 1 6 9 11 11 8 5 11 1 6 3 12 11 3
20
0 0 2 11 0 2 8 1 5 4 10 4 7 4 13 1 10 2 8 11

759833446
709820289
802116046
343692793
704373542
"""