Sum of Shortest Compressed IPv6 Lengths

An IPv6 address is essentially a 128‐bit number represented as eight groups of 16‐bit hexadecimal numbers separated by colons. In its full notation each group is represented by 4 digits (with possible leading zeroes) but in the canonical form the leading zeroes in each group are omitted (if a group is all zero, it is written as a single 0). Furthermore, a single maximal run of consecutive groups which are equal to 0 can be replaced by a double colon :: in the compressed form (if and only if the run has length at least 2, since compressing a single zero would increase the length). For example,

0000:0000:0000:0000:0000:0000:0000:0000  →  ::
0000:0001:0000:0000:0000:0001:0000:0000  →  0:1::1:0:0
0000:0001:00ab:0000:0023:0000:0a00:0e00  →  0:1:ab::23:0:a00:e00
0000:0000:00ab:0000:000a:0001:0a00:0e00  →  ::ab:0:a:1:a00:e00
0000:0000:00ab:0000:0000:0001:0a00:0e00  →  0:0:ab::1:a00:e00

Let L(x) denote the length of the minimal hexadecimal representation of a 16‐bit number x (i.e. without leading zeroes – note that 0 is represented as a single character). Thus, an uncompressed IPv6 address has length $$ \sum_{i=1}^8 L(g_i) + 7, $$ where the additional 7 are the colons between the eight groups.

If there is a block of k consecutive groups equal to 0 (with k ≥ 2) then compressing them yields an extra saving of $$ (k + (k-1)) - 2 = 2k-3. $$ (That is, the k groups, normally printed as 0:0:...:0 (a total of 2k-1 characters), are replaced by :: (2 characters). Compression can be applied at most once per address.)

Your task is to compute the sum of the lengths of the shortest compressed representations for all IPv6 addresses modulo \(10^9+7\). Note: There are \(2^{128}\) IPv6 addresses in total, so an efficient combinatorial solution is required. One hint is that the eight groups are independent except for the decision of which maximal consecutive block of zeros (if any) to compress. In particular, for each group, its minimal representation length is:

• If the value is 0, then its length is 1.
• If the value is nonzero, then its length is \(1\), \(2\), \(3\), or \(4\), depending on the magnitude (e.g. values 1 to 15 have length 1, 16 to 255 have length 2, 256 to 4095 have length 3 and 4096 to 65535 have length 4).

The compressed form is obtained by optionally replacing one maximal contiguous block of groups that are 0 (and with length at least 2) by ::.

Since the answer is huge (even larger than a 128‐bit integer), output the answer modulo \(10^9+7\).

inputFormat

This problem has no input.

outputFormat

Output a single integer, which is the sum (modulo \(10^9+7\)) of the lengths of the shortest compressed forms for all IPv6 addresses.

sample

889808443