Yuxarı və Aşağı#6852
Bir sıra {1, ..., N} ədədlərinin permutasiyası, bu ədədlərin fərqli bir sıralanmasıdır, burada hər ədəd yalnız bir dəfə görünür. Biz permutasiyanın yuxarı-seqmenti və aşağı-seqmentini aşağıdakı şəkildə təyin edirik.
Yuxarı-seqment [u_1, ..., u_N]: u_i minimum müsbət k ədədidir ki, a_i < a_{i+k} şərtini ödəyir. Əgər belə bir ədəd yoxdursa, onda u_i = N + 1 - i olur.
Aşağı-seqment [d_1, ..., d_N]: d_i minimum müsbət k ədədidir ki, a_i > a_{i+k} şərtini ödəyir. Əgər belə bir ədəd yoxdursa, onda d_i = N + 1 - i olur.
Məsələn, verilmiş permutasiya [1, 4, 3, 2, 6, 5] üçün yuxarı-seqment [1, 3, 2, 1, 2, 1] və aşağı-seqment [6, 1, 1, 3, 1, 1] olur.
Ümumiyyətlə, eyni yuxarı-seqment və aşağı-seqmenti paylaşan bir neçə permutasiya mövcuddur. Yuxarıdakı nümunə üçün, [1, 5, 4, 2, 6, 3] və [1, 5, 3, 2, 6, 4] permutasiyaları eyni yuxarı-seqment və aşağı-seqmenti paylaşır.
Sizdən verilmiş yuxarı-seqment və aşağı-seqmentə əsasən permutasiyaların sayını hesablamaq tələb olunur.
Giriş bir sıra məlumat dəstlərini ehtiva edir.
Hər dəst üç sətirdən ibarətdir. Birinci sətir bir müsbət tam ədəd N (N ≤ 17) ehtiva edir. Sonrakı iki sətir hər biri N tam ədəd ehtiva edir, burada birinci sətir yuxarı-seqmenti, ikinci sətir isə aşağı-seqmenti göstərir. Bu tam ədədlər boşluqla ayrılır.
Giriş bir sıfır ehtiva edən sətirlə tamamlanır. Bu sətir işlənməməlidir.
Hər dəst üçün, verilmiş yuxarı-seqment və aşağı-seqmentə görə mümkün permutasiyaların sayını ehtiva edən bir sətir çap edin.
Nümunə 1