Russian school winter training 2008 - 01 - Слияние последовательностей

Задача A. Слияние последовательностей ≡

задачи
видимые пробелы
простые формулы
широкий текст
редактор

Автор:	Жюри всероссийских зимних сборов школьников 2007-2008	Ограничение времени:	2 сек
Входной файл:	merge.in	Ограничение памяти:	64 Мб
Выходной файл:	merge.out
Максимальный балл:	100

Условие

Автомат получает на вход две ленты чисел, длинами N и M соответственно, и выдает одну, длиной N + M. Автомат работает по следующему принципу:

Если автомат дошёл до конца одной из лент, то на выход выдается конец второй ленты. После этого работа автомата прекращается.
Если же ни одна из лент не закончена, то с равной вероятностью на выход выдается очередное число из первой или второй ленты. После чего соответствующая лента сдвигается на одну позицию.

Например, если исходно были последовательности (1,2,3) и (1,3,4), то результатом работы автомата может быть одна из следующих последовательностей: (1,1,2,3,3,4), (1,1,2,3,4,3), (1,1,3,2,3,4), (1,1,3,2,4,3), (1,1,3,4,2,3), (1,2,1,3,4,3), (1,2,1,3,3,4), (1,2,3,1,3,4), (1,3,1,2,3,4), (1,3,1,2,4,3), (1,3,1,4,2,3), (1,3,4,1,2,3).

Формат входного файла

В первой строке будут даны два целых числа N и M. Во второй строке записаны N различных целых чисел — числа на первой ленте. В третьей строке записаны M различных целых чисел — числа на второй ленте.

Формат выходного файла

Выведите единственное целое число — количество различных последовательностей.

Ограничения

1 ≤ N ≤ 100

1 ≤ M ≤ 100

Числа по модулю не превосходят 10⁶.

Примеры тестов

№	Входной файл (`merge.in`)	Выходной файл (`merge.out`)
1	`3 3 1 2 3 1 3 4`	`12`