У нас є дві перестановки \(P\) і \(Q\) розміру \(N\) (тобто \(P\) і \(Q\) обидві є перестановками (1, 2, ...,N). Є \(N!\) можливих перестановок розміру \(N\).

Нехай серед них \(P\) та \(Q\) — \(a\)-а та \(b\)-а лексикографічно найменші перестановки відповідно. Знайдіть ∣a - b∣.

Примітки. Для двох послідовностей \(X\) і \(Y\) \(X\) називають лексикографічно меншим за \(Y\) тоді і тільки тоді, коли існує ціле \(k\), таке, що \(X_i=Y_i\) (\(1 \le i < k\)) і \(X_k < Y_k\).

Формат вхідних даних

Перший рядок містить ціле число \(N\) (\(2 \le N \le 8\))

Другий рядок містить перестановку \(P\).

Третій рядок містить перестановку \(Q\).

Числа у рядках розділяються пропуском.

Формат вихідних даних

У вихідний потік виведіть \(|a-b|\).

Примітка

До прикладу 1:

Існує 6 перестановок розміру 3: (1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2) та (3, 2, 1). Серед них (1, 3, 2) і (3, 1, 2) займають 2-е та 5-е місце в лексикографічному порядку, тому відповідь |2 - 5| = 3.

Приклад вхідних даних

3
1 3 2
3 1 2

Приклад вихідних даних

3

Приклад вхідних даних

8
7 3 5 4 2 1 6 8
3 8 2 5 4 6 7 1

Приклад вихідних даних

17517

Приклад вхідних даних

3
1 2 3
1 2 3

Приклад вихідних даних

0