Сізге ұзындығы \(n\) болатын екі алмастыру \(l\) және \(r\), сондай-ақ бүтін сан \(k\) берілген.

Мұндағы \(n\) — алмастырулардың ұзындығы.

\(p\) алмастыруы жарамды деп аталады, егер келесі екі шарт орындалса:

• \(l \le p \le r\) лексикографиялық тәртіпте;

• \(p\) алмастыруындағы инверсиялар саны \(k\)-ға тең.

Жарамды алмастырулардың санын \(998244353\) модулі бойынша табыңыз.

Ұзындығы \(n\) болатын алмастыру деп \(1\)-ден \(n\)-ге дейінгі әртүрлі бүтін сандардан тұратын массив аталады.

Еске салайық, \(a\) алмастыруы \(b\) алмастыруынан лексикографиялық түрде кіші болады, егер қандай да бір \(i\) орны табылып:

• барлық \(1 \le j < i\) үшін \(a_j = b_j\);

• \(a_i < b_i\).

\(p\) алмастыруындағы инверсия деп \((i, j)\) индекстер жұбы аталады, мұнда \(1 \le i < j \le n\) және \(p_i > p_j\).

Енгізу

Бірінші жолда екі бүтін сан \(n\) және \(k\) берілген (\(1 \le n \le 10^6\), \(0 \le k \le 5000\)).

Екінші жолда \(n\) бүтін сан \(l_1, l_2, \dots, l_n\) — \(l\) алмастыруының элементтері.

Үшінші жолда \(n\) бүтін сан \(r_1, r_2, \dots, r_n\) — \(r\) алмастыруының элементтері.

\(l\) және \(r\) ұзындығы \(n\) болатын алмастырулар екені және \(l \le r\) лексикографиялық тәртіпте болатыны кепілденеді.

Шығару

Бір бүтін санды шығарыңыз — лексикографиялық тәртіпте \(l \le p \le r\) болатын және \(p\) ішіндегі инверсиялар саны \(k\)-ға тең \(p\) алмастыруларының санын, \(998244353\) модулі бойынша.

Мысалдар

Енгізу 1

4 3
1 2 3 4
4 3 2 1

Жауап 1

6

Енгізу 2

6 5
2 1 3 4 5 6
4 2 6 1 5 3

Жауап 2

43