Böyük Bir Qala
Qədim Babil sakinləri böyük bir qüllə tikməyə qərar verdilər. Qüllə, bir-birinin üzərinə yığılmış N kubik tikinti bloklarından ibarətdir. Babil sakinləri ölkənin hər yerindən müxtəlif ölçülərdə çoxlu tikinti blokları topladılar. Son uğursuz cəhdlərindən öyrəndilər ki, əgər böyük bir bloku birbaşa çox kiçik bir blokun üzərinə qoysalar, qüllə yıxılacaq.
Hər iki tikinti bloku fərqlidir, hətta eyni ölçüdə olsalar belə. Hər tikinti bloku üçün onun yan uzunluğu verilir. Sizə həmçinin bir tam ədəd D verilir ki, onun mənası belədir: əgər A blokunun yan uzunluğu B blokunun yan uzunluğu ilə D cəminə nisbətən daha böyükdürsə, A blokunu birbaşa B blokunun üzərinə qoymağa icazə verilmir.
Bütün tikinti bloklarından istifadə edərək qülləni qurmağın mümkün olan müxtəlif yollarının sayını hesablayın. Bu say çox böyük ola biləcəyi üçün nəticəni 10^9+9 modulu ilə çıxarın.
Giriş verilənləri
Girişin birinci sətri iki müsbət tam ədəd N və D ehtiva edir: tikinti bloklarının sayı və tolerantlıq müvafiq olaraq.
İkinci sətir N boşluqla ayrılmış tam ədəd ehtiva edir; hər biri bir tikinti blokunun ölçüsünü təmsil edir.
Məhdudiyyətlər
Giriş fayllarındakı bütün ədədlər 10^9 -dan çox olmayan müsbət tam ədədlərdir.
N həmişə ən azı 2-dir.
70 xal dəyərində olan test hallarında N ən çox 70 olacaq.
Bunlardan 45 xal dəyərində olan test hallarında N ən çox 20 olacaq.
Bunlardan 10 xal dəyərində olan test hallarında N ən çox 10 olacaq.
Bəzi test hallarında etibarlı qüllələrin ümumi sayı 1000000-i keçməyəcək. Bu test halları ümumilikdə 30 xal dəyərindədir.
Son altı test hallarında (dəyəri 30 xal) N dəyəri 70-dən böyükdür. Bu test halları üçün N üçün yuxarı hədd verilmir.
Çıxış verilənləri
Tək bir sətirdə tək bir tam ədəd çıxarın: 1000000009 modulu ilə qurula bilən qüllələrin sayı.