D. Цезарийн цэргүүд

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

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

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

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

Генерал Юлий Цезарь $n_1$ ширхэг явган цэрэг, $n_2$ ширхэг морин цэрэгтэй армиа жагсаах болов. Цезарь нь $k_1$-ээс олон явган цэрэг дарааллан зогссон, эсвэл $k_2$-оос олон морин цэрэг дарааллан зогссон жагсаалд дургүй. Цезарьт таалагдахаар жагсах боломжийн тоог олно уу.

Бүх $n_1 + n_2$ цэргүүд жагсаалд оролцоно. Явган цэргүүд өөр хоорондоо ялгаагүй ба мөн адилаар морин цэргүүд өөр хоорондоо ялгаагүй гэж үзнэ.

Оролт

Нэг мөрөнд $n_1$, $n_2$, $k_1$, $k_2$ ($1 ≤ n_1, n_2 ≤ 100$, $1 ≤ k_1, k_2 ≤ 10$) өгөгдөнө. Эдгээр нь харгалзан явган цэргийн тоо, морин цэргийн тоо, явган ба морин цэргүүд тус бүрийн хамгийн уртаар дарааллан зогсож болох дарааллын урт.

Гаралт

Цезарьт таалагдах хэдэн янзын жагсаалын байрлал олдохыг $100000000$ ($10^8$) модулиар олно уу. Өөрөөр хэлвэл $k_1$-ээс олонгүй явган цэрэг, $k_2$-оос олонгүй морин цэрэг дараалж зогссон боломжийн тоо.

Орчуулсан: Б.Батхуяг

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

Оролт
2 1 1 10
Гаралт
1
Оролт
2 3 1 2
Гаралт
5
Оролт
2 4 1 1
Гаралт
0

Тэмдэглэл

Let's mark a footman as 1$, and a horseman as 2$.

In the first sample the only beautiful line-up is: 121$

In the second sample 5 beautiful line-ups exist: 12122$, 12212$, 21212$, 21221$, 22121$

Сэтгэгдлүүдийг ачааллаж байна...