Üç tərəfli Şöbə#3568
Bir ızgara W×H ölçüsündə hüceyrələrdən ibarətdir. Sol üst küncdəki hüceyrə (1, 1) nöqtəsində yerləşir. Siz hazırda (1, 1) hüceyrəsindəsiniz və məqsədiniz (W, H) hüceyrəsinə çatmaqdır. Hərəkət edərkən yalnız sol-aşağı, aşağı və ya sağ-aşağı istiqamətlərdəki qonşu hüceyrələrə keçə bilərsiniz.
Bəzi hüceyrələrdə maneələr mövcuddur və bu hüceyrələrə keçmək mümkün deyil. Eyni zamanda, ızgaranın kənarına çıxmaq da qadağandır. (1, 1) hüceyrəsində heç bir maneənin olmadığını qəbul edə bilərsiniz.
Birinci sətirdə üç tam ədəd verilmişdir: ızgaranın eni W, hündürlüyü H və maneələrin sayı N. Burada (1 ≤ W ≤ 75, 2 ≤ H ≤ 10^18, 0 ≤ N ≤ 30) şərtləri ödənilir. Sonrakı N sətirin hər biri bir maneənin yerini göstərən 2 tam ədəd ehtiva edir (x_i, y_i).
Son testdən sonra üç sıfırdan ibarət bir sətir gəlir.
Hər test üçün, testin sıra nömrəsini və (W, H) hüceyrəsinə çatmağın mümkün yollarının sayını 1000000009 modulu ilə çap edin.
Nümunə 1