Մորեխ
Մորեխը ցանկանում է կոորդինատային հարթության (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:
Ելքային տվյալներ
Ելքում պետք է արտածել մեկ թիվ ՝ տարբեր ուղիների քանակը, որոնք մորեխը կարող է անցնել ցանկալի կետին հասնելու համար:
Օրինակ
Մուտք | Ելք |
3 1 2 3 2 | 4 |
Օրինակի բացատրություն
Բոլոր հնարավոր ուղիները՝
(0,0) -> (1,0) -> (3,1)
(0,0)-> (1,1) -> (3,1)
(0,0) -> (2,0) -> (3,1)
(0,0) -> (2,1) -> (3,1)
Ենթախնդիրներ
- Ենթախնդիր 1 (10 միավոր)
N,M,A,B,K ≤ 8
- Ենթախնդիր 2 (20 միավոր)
N,M,A,B,K ≤ 50
- Ենթախնդիր 3 (25 միավոր)
N,A,K ≤ 3000, M,B ≤ 1
- Ենթախնդիր 4 (14 միավոր)
N,M,A,B,K ≤ 300
- Ենթախնդիր 5 (15 միավոր)
N,M,A,B,K ≤ 1000
- Ենթախնդիր 6 (16 միավոր)
N,M,A,B,K ≤ 3000
Constraints
Time limit: 10 seconds
Memory limit: 512 MB
Output limit: 1 MB