Otaqlar#3697
Biznesmen Petyanın yaxınlarda yeni bir ev alıb. Bu evdə bir mərtəbə var və bu mərtəbə n×m ölçülü kvadrat otaqlara bölünüb. Bu otaqlardan bəziləri yaşayış otaqları, bəziləri isə anbarlar olacaq.
Petya istəyir ki, bəzi yaşayış otaqları arasında keçidlər olsun və hər hansı bir yaşayış otağından digərinə bu keçidlər vasitəsilə yalnız bir yolla çatmaq mümkün olsun. Keçidlər yalnız qonşu otaqlar arasında, yəni ümumi divarı olan otaqlar arasında qurula bilər.
Otaqları tələb olunan şəkildə birləşdirməyin müxtəlif yollarının sayını hesablamaq lazımdır.
Giriş faylının birinci sətirində n və m (1 ≤ n, m ≤ 12) ədədləri verilir. Sonra n sətir, hər biri m simvoldan ibarət olan, evin xəritəsini təmsil edən sətirlər gəlir. "." simvolu yaşayış otağını, "*" simvolu isə anbarı göstərir.
Bir ədəd çıxarın — axtarılan sayın 10^9 ilə bölünməsindən qalan.
Nümunə 1