Զանգվածներ և բաժանարարներ
Տրված
N, M և K թվերի դեպքում կասենք, որ K երկարության զանգվածը գեղեցիկ է, եթե նրա բոլոր տարրերը M-ը չգերազանցող բնական թվեր են և այդ բոլոր տարրերի արտադրյալը հանդիսանում է N թվի բաժանարար։ Օրինակ N = 12, M = 6 և K = 4 թվերի դեպքում {1, 2, 2, 3} և {1, 1, 6, 1} զանգվածները գեղեցիկ են, իսկ {-1, 1, -6, 1}, {1, 12, 1, 1} և {1, 2, 3, 4} զանգվածները՝ ոչ։Ձեզ տրված են
N, M, և K թվեր։ Հարկավոր է հաշվել բոլոր գեղեցիկ զանգվածների քանակի՝ 109+7-ի բաժանելիս ստացվող մնացորդը։Մուտքային տվյալներ
Մուտքի միակ տողում տրված են մեկական բացատանիշերով անջատված
N, M և K բնական թվերը։Ելքային տվյալներ
Ելքում պետք է արտածել մեկ թիվ՝ բոլոր հնարավոր գեղեցիկ զանգվածների քանակի՝
109+7-ի բաժանելիս ստացվող մնացորդը։Օրինակ
Մուտք | Ելք |
6 6 1 | 4 |
12 5 2 | 12 |
2 3 1000000 | 1000001 |
Բացատրություն
Առաջին օրինակին համապատասխանող գեղեցիկ զանգվածներն են
{1}, {2}, {3}, {6} զանգվածները։ Երկրորդ օրինակին համապատասխանող գեղեցիկ զանգվածներն են {1, 1}, {1, 2}, {1, 3}, {1, 4}, {2, 1}, {2, 2}, {2, 3}, {3, 1}, {3, 2}, {3, 4}, {4, 1}, {4, 3} զանգվածները։ Երրորդ օրինակին համապատասխանող գեղեցիկ զանգվածներն են 1000000 հատ 1-ից կազմված զանգվածը և բոլոր այն 1000000 երկարության զանգվածները, որտեղ թվերից մեկը 2 է, մնացածը՝ 1։Ենթախնդիրներ
- Ենթախնդիր 0 (0 միավոր) Օրինակները,
- Ենթախնդիր 1 (10 միավոր)
K = 1, 1 ≤ N, M ≤ 1012
- Ենթախնդիր 2 (10 միավոր)
1 ≤ M, K ≤ 107, MK≤ 107, 1 ≤ N ≤ 1012
- Ենթախնդիր 3 (10 միավոր)
1 ≤ K ≤ 3, 1 ≤ N, M ≤ 109
- Ենթախնդիր 4 (10 միավոր)
1 ≤ K ≤ 30, 1 ≤ M = N ≤ 109
- Ենթախնդիր 5 (30 միավոր)
1 ≤ K ≤ 30, 1 ≤ M, N ≤ 109
- Ենթախնդիր 6 (10 միավոր)
1 ≤ K ≤ 5000, 1 ≤ M, N ≤ 109
- Ենթախնդիր 7 (10 միավոր)
1 ≤ K ≤ 106, 1 ≤ M, N ≤ 109
- Ենթախնդիր 8 (10 միավոր)
1 ≤ K ≤ 1018, 1 ≤ M, N ≤ 109։
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB