25917번 - Prime Arrangement 서브태스크

정수 $R$, $C$가 주어진다. 이어 $R\times C$개의 서로 다른 소수 $A_i$가 주어진다. 소수는 $2$ 이상이고, $1$과 자기 자신으로만 나누어지는 양의 정수를 의미한다.

길이 $R$의 순열 $P$가 주어진다. 길이 $R$의 순열은 $1$부터 $R$까지의 정수가 단 한 번씩만 존재하는 수열이다.

당신은 $R$행 $C$열의 2차원 배열에 주어진 소수들을 단 한 번씩만 사용하여 배치할 수 있다. 배열의 각 자리에 최대 하나의 소수만이 들어갈 수 있다.

소수를 배치한 이후에는 각 행마다 가중치를 얻을 것이다. $i$번째 행의 가중치는 $i$번째 행에 존재하는 모든 소수들을 한 번씩 곱한 값으로 계산된다. ($1\leq i \leq R$)

당신은 올바른 소수의 배치 중 각 행의 가중치들을 작은 순서대로 나열했을 때, $i$번째 행의 가중치가 각각 $P_i$번째에 위치하도록 하는 배치의 수를 구해야 한다.

입력은 아래와 같이 주어진다.

가능한 배치의 수를 $998\,244\,353$으로 나눈 나머지를 출력한다. $998\,244\,353$은 소수이다.

• $1 \leq R,C \leq 500$
• $2 \leq A_i < 10^7$
• $A_i$는 소수이다.
• $1 \leq P_i \leq R$