A sequence \textbf{p(1)}, \textbf{p(2)}, …, \textbf{p(N)} consisting of numbers \textbf{1}, \textbf{2}, … , \textbf{N} is called a \textit{permutation} if all elements in the sequence are different. It is said that a permutation \textbf{p} contains \textit{increasing subsequence} of \textbf{k} elements when there are numbers \textbf{1} ≤ \textbf{i_1} < \textbf{i_2} < … < \textbf{i_k} ≤ \textbf{N} such that \textbf{p(i_1)} < \textbf{p(i_2)} < … < \textbf{p(i_k)}. When a permutation p contains an \textit{increasing subsequence} consisting of \textbf{B} elements and does not contain an \textit{increasing subsequence} consisting of \textbf{B+1} elements then the number \textbf{B} is called \textit{the degree of increase} of this permutation. You need to write a program which being given a number \textbf{N} calculates the number of permutations whose \textit{degree of increase} is \textbf{B}. Since the number of such permutations might be quite big, it is necessary to calculate its remainder of integer division by \textbf{1000000000}. \InputFile The input file consists of one line. The line contains two integer numbers \textbf{N} and \textbf{B} (\textbf{1} ≤ \textbf{N} ≤ \textbf{40}, \textbf{1} ≤ \textbf{B} ≤ \textbf{5}) separated by one or more spaces. \OutputFile The output file contains one integer number which is the remainder of integer division by \textbf{1000000000} of the number of permutations whose \textit{degree of increase} is \textbf{B}.