Zindan Yaradılması#3564
Kral demon öz zindanında cəsur bir adamı məğlub etmək üçün gözləyir. Onun zindanı H×W ölçüsündə bir şəbəkədən ibarətdir. Hər hücrə dörd istiqamətdə (yəni, şimal, cənub, şərq və qərb) qonşu hücrələrlə bağlıdır və bəzi hücrələr maneələrlə doludur.
Cəsur adama hücum etmək üçün kral demon zindanda dolaşan bir xidmətçi yaratdı və göndərdi. Lakin tezliklə kral demon gördü ki, xidmətçi onun istədiyi kimi işləmir. Xidmətçi çox axmaqdır. Əgər zindanda dövri yol olsaydı, o, dövr boyunca əbədi olaraq gəzə bilərdi.
Xidmətçinin nəhayət cəsur adamı tapmasını təmin etmək üçün, kral demon hücrələr arasında divarlar tikərək bütün dövrləri aradan qaldırmağa qərar verdi. Eyni zamanda, maneələrlə dolu olmayan hər hansı iki hücrə arasında ən azı bir yolun olmasına diqqət yetirməlidir.
Sizin vəzifəniz kral demonun divarları neçə yolla tikə biləcəyini hesablayan bir proqram yazmaqdır.
Hər test halının ilk sətri zindanın hündürlüyü və eni olan iki tam ədəd H və W (1 ≤ H ≤ 500, 1 ≤ W ≤ 15) ehtiva edir. Ardınca gələn H sətir hər biri '.' (hücrədə maneə yoxdur) və ya '#' (maneə var) olan dəqiq W hərflərdən ibarətdir. Hücrədə maneə olmayan ən azı bir hücrə olduğunu qəbul edə bilərsiniz.
Giriş H=0 və W=0 olduqda bitir. Bu halda proqramınız heç bir çıxış verməməlidir.
Hər test halı üçün, bir sətirdə onun hal nömrəsini və divarların tikilə biləcəyi yolların sayını çap edin. Cavab çox böyük ola biləcəyi üçün, 1000000007 modulu ilə çıxış edin.
Nümunə 1