Զանգվածներ և բաժանարարներ

Տրված NM և K թվերի դեպքում կասենք, որ K երկարության զանգվածը գեղեցիկ է, եթե նրա բոլոր տարրերը M-ը չգերազանցող բնական թվեր են և այդ բոլոր տարրերի արտադրյալը հանդիսանում է N թվի բաժանարար։ Օրինակ N = 12M = 6 և K = 4 թվերի դեպքում {1, 2, 2, 3} և {1, 1, 6, 1} զանգվածները գեղեցիկ են, իսկ {-1, 1, -6, 1}{1, 12, 1, 1} և {1, 2, 3, 4} զանգվածները՝ ոչ։
Ձեզ տրված են NM, և K թվեր։ Հարկավոր է հաշվել բոլոր գեղեցիկ զանգվածների քանակի՝ 109+7-ի բաժանելիս ստացվող մնացորդը։

Մուտքային տվյալներ

Մուտքի միակ տողում տրված են մեկական բացատանիշերով անջատված NM և 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

To check your solution you need to sign in
Sign in to continue