Konfiqurasiyalar

Bu məsələdə sizə R \!\times\! C ölçüsündə bir şəbəkə verilir (1 \leq R \leq 10^9 və 1 \leq C \leq 10). Şəbəkədə $B$ blok (0 \leq B \leq 100) yerləşdirilib. Hər bir blok bir hüceyrədə yerləşir və bir hüceyrədə bir neçə blok ola bilər.

Sizə həmçinin $M$ eyni nişan (token) verilir. Bu nişanları birinci sətrə istədiyiniz kimi yerləşdirə bilərsiniz. Heç bir hüceyrədə bir nişandan artıq ola bilməz və blok olan hüceyrəyə nişan yerləşdirə bilməzsiniz. Yerləşdirdikdən sonra nişanları aşağıdakı qaydalara əsasən hərəkət etdirə bilərsiniz:

1. Əgər nişan $(r,c)$ hüceyrəsindədirsə, onu (r{+}1, c{-}1) və ya (r{+}1, c{+}1) hüceyrəsinə apara bilərsiniz.

2. Nişanı blok yerləşən hüceyrəyə keçirmək olmaz.

3. Nişanı kənara çıxarmağa icazə yoxdur (şəbəkənin hüdudlarından kənara çıxmaq olmaz).

4. İki və ya daha çox nişanı eyni hüceyrəyə apara bilməzsiniz.

5. Bütün nişanlar $i$-ci sətrə yerləşməlidir ki, onlardan hər hansı biri $(i+1)$-ci sətrə keçə bilsin.

S = \{(1, c_1), (1, c_2), \ldots, (1, c_M)\} olsun — siz nişanları birinci sətrə yerləşdirdiyiniz hüceyrələr çoxluğu. $W(S)$ — bu nişanları yuxarıdakı qaydalara əsasən sonuncu sətrə çatdırmaq üsullarının sayıdır. $S$ üçün mümkün bütün yerləşmələr üzrə $W(S)$-lərin cəmini tapın.

R = 2, C = 2, M = 1 və B = 0 üçün cavab 2-dir.