Մորեխը ցանկանում է կոորդինատային հարթության (0, 0) կետից հասնել (N, M) կետին ուղիղ K ցատկերի միջոցով։ Յուրաքանչյուր ցատկով մորեխը կարող է մեծացնել իր x կոորդինատը A-ից ոչ ավելի, իսկ y կոորդինատը՝ B-ից ոչ ավելի:
Ֆորմալ, եթե մորեխը գտնվում է (x,y) կետում, ապա մեկ քայլով կարող է ցատկել դեպի (x', y') կետը, եթե x ≤ x' ≤ x + A և y ≤ y' ≤ y + B
Այսինքն, մեկ ցատկով մորեխը կարող է չմեծացնել իր կոորդինատներից մեկը (կամ երկուսը), բայց կոորդինատը փոքրացնել չի կարող։
Գրեք ծրագիր, որը կգտնի տարբեր ուղիների քանակը, որոնք մորեխը կարող է անցնել սկզբնական կետից ցանկալի կետին հասնելու համար: Քանի որ պատասխանը կարող է լինել շատ մեծ թիվ, գտեք այն 1000000007-ի (10^9 + 7) բաժանելուց մնացորդը:
Մուտքային տվյալներ
Մուտքի միակ տողում տրված են հինգ ամբողջ թվեր՝ N, M, A, B և K:
Ելքային տվյալներ
Ելքում պետք է արտածել մեկ թիվ ՝ տարբեր ուղիների քանակը, որոնք մորեխը կարող է անցնել ցանկալի կետին հասնելու համար: