Company: Google_19july
Difficulty: medium
Number of sequences Problem Description You are given three integers Z , O and K . Consider every sequence of length Z + O that is made up of exactly Z zeros and exactly O ones. Two such sequences are different if they differ at any position, so there are as many of them as there are ways to choose which positions hold the zeros. Determine how many of these sequences have a longest non-decreasing subsequence of length at least K . Because the count can be very large, print it modulo 10 9 + 7. Note: a non-decreasing subsequence of a sequence a is given by indices p1 < p2 < ... < pm with a[p1] <= a[p2] <= ... <= a[pm] . Its length is m . The chosen positions do not have to be adjacent, and equal values are allowed. Input Format The first line contains a single integer T , the number of test cases. Each test case is given on the next three lines: a line containing the integer Z , the number of zeros in the sequence; a line containing the integer O , the number of ones in