- All Contests
- ProjectEuler+
- Project Euler #244: Sliders

# Project Euler #244: Sliders

# Project Euler #244: Sliders

_{This problem is a programming version of Problem 244 from projecteuler.net}

You probably know the game *Fifteen Puzzle*. Here, instead of field 4 by 4 and numbered tiles, we have field by , [] red tiles and [] blue tiles.

A move is denoted by the uppercase initial of the direction (Left, Right, Up, Down) in which the tile is slid, e.g. starting from configuration **(S)**, by the sequence **LULUR** we reach the configuration **(E)**:

(S) |
(E) |
---|---|

For each path, its checksum is calculated by pseudocode:

...

where is the ASCII value of the -th letter in the move sequence and the ASCII values for the moves are:

Letter | Code |
---|---|

L | 76 |

R | 82 |

U | 85 |

D | 68 |

For the sequence **LULUR** given above, the checksum would be .

Now, starting from given configuration **(S)**, find all shortest ways to reach given configuration **(E)**.

What is the sum of all checksums for the paths having the minimal length?

**Input Format**

First line contains the only integer .

Next lines contain configuration **(S)**.

Next lines contain configuration **(E)**.

Blue, red and white tiles are denoted by letters **B**, **R** and **W** respectively.

**Constraints**

**Output Format**

Print the only number the total sum of all checksums modulo .

**Sample Input 0**

```
2
WR
BB
RB
BW
```

**Sample Output 0**

```
18553
```

**Sample Input 1**

```
3
BBB
BWR
RRR
RBR
BWB
RBR
```

**Sample Output 1**

```
86665639
```