Description
Solutions
Count Good Strings

There is a string of length 2N containing only character A and B. The string is called good string if the following two conditions are satisfied:

  • The number of A and number of B in that string will be same and that is N, means N numbers of A and N numbers of B will be present in that string.
  • The number of A will be always greater than or equal to the number of B in any prefix string of that string.

    • Now you are given N and you need to count the number of good strings of length 2N, the answer may be very large so return the answer in modulo 10000.

    Example 1: 

    Input:  N = 3
    Output: 5 
    Explanation:
    

Here are the good strings of length 2N when N=3:
      
      
      
        
    • "AAABBB" good
      • 
        
    • "AABABB" good 
      • 
        
    • "AABBAB" good 
      • 
        
    • "ABAABB" good 
      • 
        
    • "ABABAB" good 
      • 
      
    
      
"BABABA" is not a good string because the number of Bs is greater than the number of As in the prefix "BA".
   
Therefore, the count of good strings is 5.
    Constraints:
      o_o
    Thumbnail 0
    Testcase
    Result
    Case 1

    input:

    output: