Compute the sum of the lengths of the longest increasing subsequence of each distinct permutation of (1,2,3,...,n). In other words, sum over all permutations, w of (1, 2, 3, . . . , n), LIS(w). Where LIS(w) is the length of the longest increasing subsequence of w. However, this number increases exponentially. In the problem we are interested only in the first three digits. Also, note that each subsequence does not have to be contiguous. For example, the longest increasing subsequence of (3,2,4,1,5) is (3,4,5) with length 3. Hint: You may want to compute a few small values and find a beautiful pattern!!! Input The input will consist of at most 100000 lines, each one with just the positive integer n (100 < n < 100000000). Output For each input value, output the first three digits of the sum of the lengths of the longest increasing subsequence of each permuation of (1, 2, 3, . . . , n). Sample Input 101 1101 2101 Sample Output 154 358 905