7 is a very special number. It is the smallest number that can’t be represented as a sum of fewer than four non-zero squares. It is also the smallest happy number greater than 1. 7 is considered to be magical in many cultures. In this problem, you will discover the amazing hidden magic of 7 in graph theory :-). Given a grid graph G, with dimensions 7 × n, as shown below (the vertices are at the center of the grid cells). Compute the last 4 digits of A + B + C, where A = The total number of different Perfect matchings of G. A Perfect matching is a matching which covers all vertices of G. B = The total number of different Hamiltonian cycles of G. A Hamiltonian cycle visits each vertex exactly once and comes back to the original vertex. C = The total number of different Spanning subgraphs of G, such that every connected component of each Spanning subgraph is a cycle. Input The input will consist of at most 100 lines with the value of n on each line. All numbers fit into unsigned 64 bit integers. Output For each line of input, output the answer on a single line. If there are fewer than 4 digits in A + B + C , pad to 4 digits with leading 0’s, otherwise output the last 4 digits as described above. Sample Input 1 2 6 10 Sample Output 0000 0030 5900 5765