SPOJ in Armenian

Դիցուք ունենք K տառ պարունակող այբուբեն: Օրինակ, եթե K = 4, այբուբենը կարող է լինել {a,b,c,d}, և bbcac-ն այդ այբուբենով կազմված բառ:

Տրված S բառի համար, count(S, k)-ով նշանակենք k  տառի հանդիպումների քանակը S-ում: Օրինակ` count(bbcac, b) = 2 և count(bbcac, a) = 1:

S  բառի վերջից սիմվոլներ հեռացնելուց հետո ստացված բառը կանվանենք S–ի նախածանց (prefix): Օրինակ` acb –ի նախածանցներն են a-ն, ac-ն, և acb-ն:

Կասենք, որ S-ը ունի Գեղեցիկ նախածանցներ, եթե ցանկացած P նախածանցի և k1, k2 տառերի համար |count(P, k1) - count(P, k2)| <= 2: Օրինակ` bbcac-ն ունի գեղեցիկ նախածանցներ, բայց abbbc  չունի քանի որ count(abbb, b) = 3 և count(abbb, c) = 0:

Անհրաժեշտ է գտնել K չափի այբուբենում L երկարությամբ բոլոր գեղեցիկ նախածանց ունեցող բառերի քանակը: Քանի որ այդ քանակը կարող է շատ մեծ լինել, անհրաժեշտ է արտածել 1000000007-ի վրա բաժանելուց ստացված մնացորդը:

Մուտքը

Մուտքում տրված են L և K, 1<= L <= 10¹⁸ and 1 <= K <= 50 ամբողջ թվերը:

Ելքը

Ելքային ֆայլում անհրաժեշտ է արտածել մեկ ամբողջ թիվ - L երկարությամբ գեղեցիկ նախածանց ունեցող բառերի քանակը K տառ ունեցող այբուբենում: Քանի որ քանակը կարող է շատ մեծ լինել, անհրաժեշտ է արտածել 1000000007-ի վրա բաժանելուց ստացված մնացորդը:

Օրինակ

Մուտքը.
4 2

Ելքը.
12