Increasing Paths, part 2

You are given a grid of at most 15×15 cells, each with a value in 0..65535. A path is a sequence of at least two cells in which consecutive cells must be adjacent up, down, left or right, and each value is strictly greater than the previous one. Different position sequences count as different paths. Count the total number of increasing paths; Part 2 guarantees the answer does not exceed 20,000,000,000, so 64-bit integers are required.

The source example's grid is unchanged, but the upstream output 601079908 does not agree with the rules. An independent reverse DFS and an independent ascending-order dynamic programming both give 600537344; this site corrects the public answer to 600537344 and keeps the discrepancy in the source evidence.

The original is a function-style problem with no standard input/output protocol; this site adds the protocol below.

输入格式

The first line contains the number of rows R (1..15); each following line gives the number of columns Cᵢ (1..15), then the Cᵢ integers of that row (0..65535). Rows may have different lengths; only the given cells exist.

输出格式

Output the total number of strictly increasing paths of length at least 2.

样例 1

输入：

15
15 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
15 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
15 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
15 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
15 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
15 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
15 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
15 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
15 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
15 11 10 11 12 13 14 15 16 17 18 19 20 21 22 23
15 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
15 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
15 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
15 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27
15 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28

输出：

600537344

样例说明

Part 2 of the source problem only raises the path-count limit to 20 billion; the path and grid rules are inherited from Part 1.