سام و خواهرش سارا یک میز n×m خانهای دارند. آنها میخواهند تمام خانههای میز را با دو رنگ قرمز و آبی رنگ کنند. طبق یک باور شخصی، آنها میخواهند رنگآمیزی طوری باشد که در پایان، هر مربع 2×2 از میز تعدادی فردی خانهی قرمز داشته باشد (یعنی یا یکی یا سه تا). بهعنوان مثال، یک رنگآمیزی معتبر یک جدول 5×3 در شکل زیر نمایش داده شده است.
متأسفانه، شب گذشته، یک غریبه تعدادی از خانههای میز را با قرمز و تعداد دیگری از خانهها را با آبی رنگ کرده است! سام و سارا اکنون میخواهند بدانند آیا میشود سایر خانههای میز را طوری رنگ کرد که در نهایت، رنگآمیزی کل میز مطابق با خواستِ باورشان باشد یا نه؟ و اگر این امر امکانپذیر است، به چند روش میتوان خانههای باقیمانده را طوری رنگ کرد که در هیچ مربع 2×2 ای، زوج تا خانهی قرمز یافت نشود.
در یک سطر تعداد راههای رنگآمیزی میز (که آن را W مینامیم) به پیمانهی 109 را بنویسید. یعنی اگر W مساوی یا بیشتر از 109 است، باقیماندهی تقسیم آن بر 109 را بنویسید.