관객 대기줄

당신은 콘서트장에서 관객 대기줄을 정리하는 직원입니다. 줄에 선 사람은 각자 좌석 번호가 적힌 티켓을 한 장씩 가지고 있습니다. 좌석 번호는 1부터 $n$까지의 정수이며 중복되지 않습니다. 인기 많은 공연이라 모든 좌석이 예약되어 있어, 정확히 $n$명이 한 줄로 서 있습니다.

그림 D-1: 관객 대기줄의 예시 (샘플 입력의 첫 번째 데이터셋).

당신의 일은 줄을 여러 지점에서 나눠, 나뉜 각 부분 줄을 서로 다른 입장 게이트로 보내는 것입니다. 관객들은 예의 바르게 줄을 지키므로 각 부분 줄 안의 순서는 그대로 유지됩니다. 게이트는 $k$개이므로 줄은 최대 $k$개의 부분 줄로 나눌 수 있습니다. 부분 줄의 길이는 제각각일 수 있지만 빈 부분 줄은 허용되지 않습니다.

그림 D-2: 줄을 나누는 예시.

부분 줄이 최대 $k$개 만들어지더라도 관객은 한 번에 한 명씩 입장합니다. 각 줄의 맨 앞에 선 사람들 가운데 좌석 번호가 가장 작은 사람이 먼저 입장합니다. 이후의 입장도 같은 방식으로 정해집니다. 즉, 그 시점에 줄 맨 앞에 선 사람 중 좌석 번호가 가장 작은 사람이 다음으로 들어갑니다.

그림 D-3: 입장 순서의 예시.

입장 순서는 줄을 어떻게 나누느냐에 따라 달라집니다. 서로 다른 방식으로 나눠도 같은 입장 순서가 나올 수 있습니다. 위 예시에서 [4 2], [3], [5], [1]로 나누면 같은 순서가 됩니다.

대기줄의 초기 순서와 관객의 최종 입장 순서가 주어졌을 때, 주어진 최종 입장 순서가 나오도록 줄을 나누는 방법이 몇 가지인지 구하십시오. 같은 방식으로 줄을 나눴다면, 부분 줄을 게이트에 배정하는 방법이 달라도 서로 다른 방법으로 세지 않습니다.

입력은 여러 개의 데이터셋으로 이루어지며, 각 데이터셋은 다음 형식을 따릅니다.

n k
s1 ... sn
t1 ... tn

정수 $n$과 $k$는 $1 \le k \le n \le 10^4$을 만족합니다. $n$은 줄에 선 사람 수이고, $k$는 게이트 수입니다. 수열 $s_1 \dots s_n$은 대기줄의 초기 순서를 나타내는 1부터 $n$까지의 순열입니다. 수열 $t_1 \dots t_n$도 1부터 $n$까지의 순열이며, 최종 입장 순서를 나타냅니다.

입력의 끝은 0 0 줄로 표시됩니다. 데이터셋은 50개를 넘지 않습니다.

각 데이터셋에 대해, 문제에서 설명한 방식으로 줄을 나누는 방법의 수를 한 줄에 출력합니다. 방법의 수가 매우 클 수 있으므로 소수 998 244 353으로 나눈 나머지를 출력합니다.