Програмчлалын олимпиадын бодлогын архив

Автоматын оролт руу N болон M урттай хоёр тууз ордог. Эдгээр тууз бүр дээр харгалзан 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).

Input

Эхний мөрөнд N, M хоёр бүхэл тоо өгөгдөнө (1<=N<=100, 1<=M<=100).

Хоёр дахь мөрөнд N ширхэг бүхэл тоонууд өгөгдөх ба энэ нь эхний туузан дээрх тоонууд юм.

Гурав дахь мөрөнд M ширхэг бүхэл тоонууд өгөгдөх ба энэ нь хоёр дахь туузан дээрх тоонууд.

Туузан дээрх тоонууд модулиараа 10⁶ - ээс хэтрэхгүй.

Output

Автомат хэдэн ялгаатай гаралт гаргаж болохыг илэрхийлэх нэг бүхэл тоог гаргана.

Example

Input:
3 3
1 2 3
1 3 4

Output:
12