Adjacent Towers of Hanoi Puzzle

The Towers of Hanoi is a famous mathematical puzzle consisting of three rods and \(n\) disks with diameters \(1, 2, \ldots, n\). In a valid configuration, each rod contains some disks, stacked in order of decreasing diameter from bottom to top (i.e. the smallest disk is always on top).

A valid move consists of taking the smallest disk from a rod and placing it on top of an adjacent rod. In this variation, disks can only be moved between adjacent rods, meaning you can only move a disk between rod 1 and rod 2 or between rod 2 and rod 3, but not directly between rod 1 and rod 3. Moves must always preserve the order such that no larger disk is ever placed on top of a smaller disk.

Given two valid configurations (an initial configuration and a target configuration), your task is to determine the minimum number of moves required to transform the initial configuration into the target configuration. Since the result can be large, return the answer modulo \(998\,244\,353\).

The configurations are given as follows: each configuration consists of three lines corresponding to rods 1, 2, and 3. Each line lists the disks on that rod from the bottom to the top. If a rod is empty, a single '-' is provided instead.

inputFormat

The input consists of 7 lines:

1. The first line contains an integer \(n\) (the number of disks).
2. Line 2: The initial configuration of rod 1 (disks separated by spaces from bottom to top, or '-' if empty).
3. Line 3: The initial configuration of rod 2.
4. Line 4: The initial configuration of rod 3.
5. Line 5: The target configuration of rod 1.
6. Line 6: The target configuration of rod 2.
7. Line 7: The target configuration of rod 3.

Each disk is identified by its diameter (an integer from 1 to \(n\)). Note that in a valid configuration, all disks appear exactly once across the three rods.

outputFormat

Output a single integer: the minimum number of moves required to reach the target configuration from the initial configuration, modulo \(998\,244\,353\).

sample

1
1
-
-
-
-
1

2