E. Ready... Set... Go!
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

In an orienteering competition, a course is described by a sequence of controls. A competitor must visit the controls in the given order. Each control is denoted by a unique positive integer. The pair of adjacent controls in a sequence is called a leg.

For a mass-start race, course setters often make the race pass in two laps. Different competitors may receive different combinations of parts of these laps, so that they can't simply follow each other. Such variations are made in such way that after both laps every runner completed the same set of legs, but did it in a different order.

You are given two sequences of controls, which describe two laps of one of the runners. It is guaranteed that:

  • Each lap is a sequence of control points that starts in the start control point and ends in the finish control point.
  • There is no control point that is visited twice during the single lap
  • There are some control points that are common between laps. The relative order of common control points is the same for the two laps.
  • Each leg is present only once in the union of the two laps.

Given two laps for one of the competitors, determine the total number of variations possible for the race. Each variation should respect the given constraints, and union of the laps should have the same set of legs.

Compute the number of possible variations modulo $$$998244353$$$.

Input

The first line contains two integers $$$n$$$ and $$$m$$$ ($$$2 \le n, m \le 200000$$$) — the lengths of the two laps.

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — the control points of the first lap.

The third line contains $$$m$$$ integers $$$b_1, b_2, \dots, b_m$$$ ($$$1 \le b_i \le 10^9$$$) — the control points of the second lap.

It is guaranteed that:

  • All $$$a_i$$$ are distinct.
  • All $$$b_i$$$ are distinct.
  • $$$a_1 = b_1$$$ and $$$a_n = b_m$$$.
  • If a value appears in both sequences, then the relative order of such values is the same in both sequences. There is no pair of adjacent values in the common sequence that is adjacent in both $$$a$$$ and $$$b$$$.
Output

Output a single integer — the number of valid variations modulo $$$998244353$$$.

Examples
Input
5 6
1 2 4 5 8
1 3 4 6 7 8
Output
4
Input
2 3
6 7
6 1 7
Output
2
Note

Possible variations for the sample test are:

    • $$$1 \to 2 \to 4 \to 5 \to 8 $$$
    • $$$1 \to 3 \to 4 \to 6 \to 7 \to 8 $$$
    • $$$1 \to 3 \to 4 \to 5 \to 8 $$$
    • $$$1 \to 2 \to 4 \to 6 \to 7 \to 8 $$$
    • $$$1 \to 2 \to 4 \to 6 \to 7 \to 8 $$$
    • $$$1 \to 3 \to 4 \to 5 \to 8 $$$
    • $$$1 \to 3 \to 4 \to 6 \to 7 \to 8 $$$
    • $$$1 \to 2 \to 4 \to 5 \to 8 $$$