Problem B
Baseball Court

Mynd tekin af commons.wikimedia.org.

Eftir löng fundarhöld er NCPC dómnefndin búin að ákveða að það að koma blóðinu af stað hjá keppendum myndi gefa af sér betri keppnir. Því var ákveðið að það að keppa í einhverri íþrótt fyrir keppni, bara upp á sigurstolt, væri góð hugmynd. Því þarf að velja vettvang og íþrótt. Annað af þessu er auðveldlega leyst með því að draga miða af handahófi úr hatti, sem verður til þess að hafnarbolti verður fyrir valinu. Þá þarf bara að útbúa leikvöll. NCPC dómnefndin hefur aðgang að rétthyrndu landsvæði sem er $a$ sinnum $b$ metrar að stærð. Einnig eru þeir með $N$ gervigrasferninga af stærð $1$ sinnum $1$ meter sem þeir geta raðað á landsvæðið til að mynda leiksvæði. Alla grasferninga verður að raða niður með hliðar sínar samsíða hliðum landsvæðisins.

Suðvesturhorn landsvæðisins er valinn sem kylfingshorn. Til að niðurröðun grasferningana sé gild þurfa tvö skilyrði að vera uppfyllt. Í fyrsta lagi þarf sérhver suður- og vesturhlið grasfernings að annað hvort liggja upp að öðrum grasferningi eða jöðrum landsvæðisins. Þetta er svo að hafnarboltinn geti ekki farið inn og útfyrir leiksvæðið þrátt fyri að fylgja beinni línu. Í öðru lagi þurfa allir grasferningar sem hafa ekki aðlægan grasferning til norðurs eða austurs að vera í sömu Manhattan-fjarlægð frá kylfingshorni. Þetta er svo allar áttir séu jafn góðar frá sjónarmiði kylfingsins.

Verkefni þitt er að finna fjölda leiða sem má raða niður grasferningunum svo það sé gert með gildum hætti.

Inntak

Fyrsta lína inntaksins inniheldur eina jákvæða heiltölu $N$ ($1 \leq N \leq 10^4$), fjölda grasreita sem á að nota. Seinni lína inntaksins inniheldur jákvæðar heiltölur $a$ og $b$ ($1 \leq a,b \leq 10^4$), sem gefur stærð landsvæðisins sem má raða niður grasferningunum innan.

Úttak

Prentið fjölda leiða til að raða niður grasferningunum með gildum hætti. Það verður að nota alla $n$ grasferninga. Þar sem þessi tala gæti verið mjög stór, prentið hana mátaða við $10^9 + 7$.

15
3 8

3

15
3 5

1

15
3 4

0