Read problems statements in Russian here 
Chef has a special affection for sets of binary strings of equal length which have same numbers of 1's. Given three integers n, k and m, your task is to find the the lexicographically  m^{th} smallest string among strings  which have length n and have k 1's. If no such string exists output -1. 

------ Tips:  ------ 

To see what lexicographic order means . See http://en.wikipedia.org/wiki/Lexicographical_{order}

------ Input ------ 

Input description.

The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows:
The first and only line of each test case contains three space separated integers N ,  K  and  M 

------ Output ------ 

For each test case output the answer on a separate line .

------ Constraints ------ 

$1 ≤ T ≤ 10$
$1 ≤ N ≤ 350$
$1 ≤ K ≤ N$

------ Example ------ 

Input:
1
3 2 2

Output:
101

------ Explanation ------ 

Example case 1. The set of strings in lexicographic order is "011", "101", and "110" 

------  Scoring  ------ 

Subtask 1 (41 point):

$1 ≤ N ≤ 20$

Subtask 2 (59 points):

$1 ≤ N ≤ 350$

Source: codechef | Difficulty: HARD
Tags: Dynamic programming

Bit manipulation

Combinatorics

Mathematics


Solutions:
def combi(n, k):
	res = 1
	for i in range(k):
		res *= n - i
	for i in range(k):
		res //= i + 1
	return res
T = int(input())
for case in range(T):
	(n, k, m) = map(int, input().split())
	if combi(n, k) < m:
		print(-1)
		continue
	b = []
	for i in range(n):
		rem_bits = n - i
		if rem_bits == k or combi(rem_bits - 1, k) < m:
			b.append('1')
			m -= combi(rem_bits - 1, k)
			k -= 1
		else:
			b.append('0')
	print(''.join(b))


import math
temp = 1
fact = [1]
for i in range(1, 351):
	temp *= i
	fact += [temp]

def bino(a, b):
	return fact[a] // (fact[a - b] * fact[b])

def find(n, k, m):
	temp = bino(n, k)
	if temp < m:
		return -1
	elif temp == m:
		return '1' * k + '0' * (n - k)
	if m == 1:
		return '0' * (n - k) + '1' * k
	for i in range(k, n + 1):
		if bino(i, k) >= m:
			break
	index = i
	temp = find(index - 1, k - 1, m - bino(index - 1, k))
	return '0' * (n - index) + '1' + temp
for _ in range(int(input())):
	(n, k, m) = list(map(int, input().strip().split(' ')))
	print(find(n, k, m))


tests = int(input())
MAXN = 400
c = [[-1 for _ in range(MAXN)] for _ in range(MAXN)]

def cnk(n, k):
	if k > n:
		return 0
	if k == 0 or n == k:
		return 1
	if c[n][k] != -1:
		return c[n][k]
	c[n][k] = cnk(n - 1, k) + cnk(n - 1, k - 1)
	return c[n][k]
for it in range(tests):
	(n, k, m) = map(int, input().split())
	x = m
	left = k
	s = ''
	if cnk(n, k) < m:
		print(-1)
		continue
	for i in range(n):
		if cnk(n - i - 1, left) < x:
			s += '1'
			x -= cnk(n - i - 1, left)
			left -= 1
		else:
			s += '0'
	print(s)