Krossvordlar#9688
Parişə daha çox turist cəlb etmək üçün Anna Luvr-un fasadında gecə nəhəng işıq-musiqi şousu təşkil etməyi planlaşdırır. Fasadlarda pəncərələr yerləşir, bu pəncərələr müxtəlif səviyyələrdə düzülüb həm üfüqi, həm də şaquli şəkildə bərabərdir.
Annaya pəncərələrdə nəhəng hərflər — hər pəncərədə bir hərf — nümayiş etdirmək ideyası gəldi ki, həm üfüqi, həm də şaquli şəkildə mənalı sözlər əmələ gəlsin.
Bir fasadda pəncərələr sətirdən və sütundan ibarət düzbucaqlı şəbəkə əmələ gətirir.
Anna hazırlayıb:
uzunluğunda olan sözlərin siyahısı (onlar şaquli şəkildə nümayiş etdiriləcək),
uzunluğunda olan sözlərin siyahısı (onlar üfüqi şəkildə nümayiş etdiriləcək).
Sizin vəzifəniz şəbəkəni elə doldurmaq üçün müxtəlif yolların sayını müəyyən etməkdir ki:
hər bir sıra düzgün üfüqi söz əmələ gətirsin,
hər bir sütun düzgün şaquli söz əmələ gətirsin.
Gərək n \times m ölçüsündə olan müxtəlif hərf şəbəkələrinin sayını hesablayasınız ki:
soldan sağa oxunan sətirlərinin hər biri üfüqi siyahıdan olan bir söz olsun;
yuxarıdan aşağıya oxunan sütunlarının hər biri şaquli siyahıdan olan bir söz olsun.
İki şəbəkə ən azı bir hüceyrədə fərqlənirsə, onlar müxtəlif hesab edilir.
Giriş məlumatları aşağıdakı formatda verilir:
birinci sətirdə iki tam ədəd n~(2 \le n \le 4) və verilmişdir;
ikinci sətirdə iki tam ədəd m~(2 \le m \le 4) və b~(1 \le a \times b \le 1008016) verilmişdir;
sonrakı sətirdə uzunluğu olan sözlər (şaquli sözlər) yazılmışdır;
sonrakı sətirdə uzunluğu olan sözlər (üfüqi sözlər) yazılmışdır.
Məhdudiyyətlər:
bütün sözlər yalnız kiçik ingilis hərflərindən (–) ibarətdir;
hər siyahıda təkrarlanan sözlər yoxdur;
sözlər müxtəlif sətirlərdə və ya sütunlarda bir neçə dəfə istifadə oluna bilər.
Xüsusi hal. Əgər n = m, onda:
əgər şaquli siyahıdan olan söz üfüqi siyahıda yoxdursa, onu üfüqi şəkildə istifadə etmək olmaz;
əgər üfüqi siyahıdan olan söz şaquli siyahıda yoxdursa, onu şaquli şəkildə istifadə etmək olmaz.
Fərqli düzgün hərf şəbəkələrinin ümumi sayını çap edin.
Nümunə 1:
Nümunə 2:
Nümunə 1
Nümunə 2