State of the Art Paint Combinations

Problem Statement

State of the Art Being a painter, Bruce thought of a new and futuristic idea for his artwork. He has X different paints on a palette and wants to create a painting with new paint combinations of the existing paints. He can utilize at most Y different paints for crafting a new paint combination. Your task is to help Bruce find the number of different paint combinations he can craft from the existing paints on the palette, and return an integer value representing the number of paints (new combinations and the existing paints). Two combinations are considered different when the sets of paints used are different; the volume of paint does not matter, and the order in which the paints are mixed does not matter. A combination that uses a single paint is exactly one of the existing paints, so those are counted as well. Because the count grows very quickly, return the answer modulo 10000 . Input Format The input consists of exactly two lines. Line 1: an integer X , the number of different paint