E. Васили баавгай ба квадратуудыг будах

хугацааны хязгаарлалт 2 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Васили баавгайд түүний дуртай $n$ болон $k$ гэсэн 2 бүхэл тоо мөн нэг харандаа байжээ. Үүний хажуугаар түүнд ялгаатай өнгийн усан будгууд агуулсан $k$ ширхэг сав байв. Бүх савнууд нь ямар нэгэн байдлаар $1$-ээс $k$ хүртэл ($1$ болон $k$ нь өөрсдөө орно) дугаарлагдсан. $i$ дугаартай сав нь $i$-дахь өнгийн будаг агуулах юм.

Эхлээд баавгай харандаагаа аван координатын хавтгай дээр 4-н хэрчим зурав. Тэдгээр нь бүгд $(0, 0)$ цэг дээр төгсгөлтэй ба тэдгээр нь $(0, 2^{n})$, $(0,  - 2^{n})$, $(2^{n}, 0)$, $( - 2^{n}, 0)$ гэсэн цэгүүд дээр эхлэлтэй байна. Дараа нь $i = 1, 2, ..., n$ бүрийн хувьд баавгай 2 квадрат зурав. Эхний квадрат нь дараах координатууд дээр оройтой байна: $(2^{i}, 0)$, $( - 2^{i}, 0)$, $(0,  - 2^{i})$, $(0, 2^{i})$. 2-дахь квадрат нь дараах координатууд дээр оройтой байна: $( - 2^{i - 1},  - 2^{i - 1})$, $( - 2^{i - 1}, 2^{i - 1})$, $(2^{i - 1},  - 2^{i - 1})$, $(2^{i - 1}, 2^{i - 1})$. Үүний дараа баавгай өөр нэгэн квадрат зурав: $(1, 0)$, $( - 1, 0)$, $(0,  - 1)$, $(0, 1)$. Дээр дурдсан бүх цэгүүд нь цэгүүдийн олонлог $A$-г үүсгэх юм.

$n = 0$ үед эцсийн зураг нь дээрх байдлаар харагдана.

$n = 2$ үед эцсийн зураг нь дээрх байдлаар харагдана.

Баавгай эцсийн зургийг $k$ үйлдлээр будахаар шийджээ. $i$-дахь үйлдэл нь дараах үе шатуудаас тогтоно:

  1. Баавгай эцсийн зурган дээрээс сонгогдсон цэгүүдийн дурын 2 цэгийн хооронд хэрчим байхаар $А$ олонлогт байх ялгаатай 3-н цэгийг сонгоно. Дараа нь сонгогдсон цэгүүд болон хэрчмүүдээр хүрээлэгдсэн ямар нэг өмнө нь будагдсан цэгүүд агуулаагүй талбайг тэмдэглэнэ.
  2. Баавгай өгөгдсөн цэгүүд болон хэрчмүүдээр хүрээлэгдсэн талбайг $i$-дахь өнгөөр будна.

$k$-дахь үйлдлийн дараа зургийн зарим хэсэг нь будагдаагүй үлдсэн байж болохыг анхаарна уу.

Баавгай танаас түүний зургийг будах хэчнээн янзын ялгаатай аргууд байгааг тооцоолохыг хүсжээ. Зургийг будах арга нь алхам болгондоо түүний сонгосон цэгүүдийн 3-н элементтэй олонлогуудын дараалал байх юм: Хэрэв 2 дарааллын $i$-дахь гишүүд буюу 3-н элементээс тогтох 2 олонлог нь давхцахгүй байх $i$ ($1 ≤ i ≤ k)$ тоо оршин байвал уг 2 дарааллыг ялгаатай гэж үзнэ. Хайж буй тоо нь маш том тоо байж болох тул та уг тоог $1000000007$ ($10^{9} + 7$)-д хуваан үлдэгдлийг нь тооцож олно уу.

Оролт

Эхний мөрөнд нэг зайгаар тусгаарлагдсан 2 бүхэл тоо $n$ болон $k$ өгөгдөнө ($0 ≤ n, k ≤ 200$).

Гаралт

Бодлогын хариултыг $1000000007$ ($10^{9} + 7$) модулаар бодсон утга болох яг ганц бүхэл тоог хэвлэнэ үү.

Орчуулсан: Баатархүү

Жишээ тэстүүд

Оролт
0 0
Гаралт
1
Оролт
0 1
Гаралт
8
Оролт
0 2
Гаралт
32
Оролт
1 1
Гаралт
32
Сэтгэгдлүүдийг ачааллаж байна...