| G. Magical Seven |
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 x n, as shown below. 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 paths of G. A Hamiltonian path visits each vertex exactly once.
C = The total number of different Spanning subgraphs of G, such that every connected component of each Spanning subgraph is a cycle.
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.
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.
1 2 6 10
0000 0030 5900 5765