As is known to all，for a form a*x + b*y = c indeterminate equation where a ,b ,c ,x ,y are all integers, when given a , b ,c ,we can use the Extended Euclidean algorithm to solve it. We must determine whether there is a solution for it before solving this equation.It is very easy for you, isn't it? Now we come to think about a more in-depth question，for a form such as a1*x1 + a2*x2 + a3*x3 + ... + an*xn + k*M = T indeterminate equation, we call it Multi-Equation ,here n ,M ,T are constant integers, other numbers are all integers. For each ai(1 <= i <= n),the value of ai is between 1 and M(includes 1 and M). Under the above condition，how many combinations of ai which will make it true that there will be at least one solution to the Multi-Equation.

Multi test cases，each case contains there integers on one line ,represents n,M,T，separated by space. Range of data: 0 <= n <= 15, 1 <= M，T <= 100000000 Process to the end of file。

Output the result of how many combinations of ai which will make it true that there will be at least one solution to the Multi-Equation.

For the first test case , there will be 2 combinations ,the detail combinations are (1),(2) For the second test case , there will be 8 combinations ,the detail combinations are (1,1),(1,2),(1,3),(2,1),(2,2),(2,3),(3,1),(3,2)

cww