Baş İnstallyatorun Sınağı#1439
"Baş İnstallyatorun Sınağı" televiziyada ən məşhur tikinti yarışmasıdır! Bu günkü buraxılışda iştirakçıları unikal bir tapşırıq gözləyir: onlar N \times M metr ölçülü düzbucaqlı döşəməni örtməlidirlər. Əvvəlcə, təşkilatçılar standart 10 \times 20 sm-lik plitələrdən istifadə etməyi təklif etdilər, lakin xarizmatik aparıcı başqa bir fikir irəli sürdü.
"Standart plitələr? Bu, bizim baş ustalar üçün çox asan olar! Gəlin bunu maraqlı edək — iştirakçılar yalnız 1 \times K metr ölçülü böyük taxtalardan istifadə edə bilərlər, burada kifayət qədər böyük olmalıdır ki, 2 \cdot K > N!"
"Bəs iştirakçılar hansı düzülüş üçün çalışmalıdırlar?" — oyun dizayneri, aparıcının növbəti addımını artıq təxmin edərək, soruşdu.
"Çox düzülüş mümkündürmü?"
"Çox-çox."
"Mükəmməl! Dəqiq neçə düzülüşün mümkün olduğunu mənə de, biz də həmin rəqəmi ekranımıza çıxaraq və nəticələri açıqlamazdan əvvəl gərginliyi artıraq!"
"Niyə belə bir sual verdim?" deyə oyun dizayneri kalkulyatora əl uzadaraq düşündü. İndi sən ona kömək edib sayını tapmalısan!
Bir proqram yaz ki, giriş kimi , və tam ədədlərini qəbul edib, N \times M metr ölçülü döşəmənin 1 \times K metr ölçülü taxtalarla neçə müxtəlif üsulla örtülə biləcəyini qaytarsın. Taxtaların kənarları döşəmənin kənarlarına paralel qoyulmalıdır.
Giriş üç sətri əhatə edir. Hər sətrin özündə bir tam ədəd var: — döşəmənin eni (metrlə), — döşəmənin uzunluğu (metrlə), — hər taxtanın uzunluğu (metrlə). Bütün ədədlər müsbətdir və -dən böyük deyil. həmişə 2 \cdot K-dən kiçikdir. , və elə verilmişdir ki, bütün örtmə üsullarının sayı 2^{63}-1-dən çox olmur.
Döşəmənin neçə müxtəlif üsulla örtülə biləcəyini göstərən bir tam ədəd çap et.
Nümunə 1