Ақтау жағалауы

Ұпайлар: 100 (partial)

Уақыт шектеуі: 1.0s

Жад шектеуі: 512M

Author:

Problem type

Каспий теңізінің жағалауында орналасқан Ақтау қаласы өзінің әдемі жағалауымен танымал. $90$ -жылдары тұрғындар жағалауға ерекше жарық инсталляциясын жасауға шешім қабылдап, бойына $n$ декоративті шам орнатты. Әр шам ағылшын әліпбиінің алғашқы $k$ әрпінің бірінің пішініне ие ( $a, b, c, \dots$ ).

Жылдар өте жарықтандыру жүйесі бірнеше рет жаңартылды, енді қалалық билік әр шамды қалауы бойынша қосып немесе өшіре алады.

Қалалық туристік агенттік зерттеу жүргізіп, үздіксіз жарықтандырылған бөліктер туристер үшін ерекше тартымды екенін анықтады. Агенттік жағалаудың тартымдылығын бағалау жүйесін жасап шығарды: ұзындығы $i$ болатын үздіксіз жарықтандырылған бөліктің құндылығы $c o s t_{i}$ деп белгіленген.

Жағалаудың жалпы тартымдылығы – барлық үздіксіз жарықтандырылған бөліктердің құндылықтарының қосындысы. Мысалы, егер қатарынан екі шам жанып тұрса, содан кейін аралықтан кейін тағы үш шам жанып тұрса, онда жалпы құндылық $c o s t_{2} + c o s t_{3}$ болады.

Қала әкімі барлық рұқсат етілген жарықтандыру конфигурацияларының жиынтық тартымдылығын білгісі келеді. Конфигурация рұқсат етілген болып есептеледі, егер $k$ түрлі шам пішінінің әрқайсысының кемінде біреуі жанып тұрса. Мұндай конфигурациялар саны өте көп болуы мүмкін болғандықтан, нәтижені $10^{9} + 7$ модулі бойынша шығарыңыз.

Мысал түсіндірмесі:

Қарапайым жағдайды қарастырайық: жағалауда пішіндері aab болатын үш шам орнатылған (яғни, алғашқы екеуі 'a' пішінді, ал үшіншісі 'b' пішінді). Агенттік үздіксіз жарықтандырылған бөліктердің құндылығын келесідей бағалады: $c o s t = [1, 2, 3]$ , мұнда $c o s t_{i}$ — ұзындығы $i$ болатын жарықтандырылған бөліктің құндылығы.

Мүмкін болатын рұқсат етілген конфигурациялар (кемінде бір 'a' және бір 'b' шамы жануы тиіс):

Бірінші және үшінші шамдар жанып тұр: a_b. $c o s t_{1} + c o s t_{1} = 1 + 1 = 2$
Екінші және үшінші шамдар жанып тұр: _ab. $c o s t_{2} = 2$
Барлық шамдар жанып тұр: aab. $c o s t_{3} = 3$

Осы конфигурациялардың тартымдылықтарының қосындысы: $2 + 2 + 3 = 7$ .

Енгізу

Бірінші жолда екі бүтін сан $n$ және $k$ ( $1 \leq k \leq n \leq 7 \cdot 10^{5}, k \leq 26$ ) беріледі — шамдар саны және шамдардың әртүрлі пішіндерінің саны.

Екінші жолда ұзындығы $n$ болатын $s$ жолы беріледі, онда әрбір $s_{i}$ — $i$ -ші шамның пішінін білдіретін алғашқы $k$ ағылшын әрпінің бірі.

Үшінші жолда $n$ бүтін саны беріледі: $c o s t_{1}, c o s t_{2}, \dots, c o s t_{n}$ $(0 \leq c o s t_{i} \leq 10^{9})$ . Мұнда $c o s t_{i}$ — ұзындығы $i$ болатын жарықтандырылған бөліктің құндылығы.

Шығару

Бір бүтін санды шығарыңыз — барлық мүмкін рұқсат етілген жарықтандыру конфигурацияларының жиынтық тартымдылығын $10^{9} + 7$ модулі бойынша.

Бағалау жүйесі

Бұл есеп $6$ ішкі есептен тұрады.

Ішкі есеп	Қосымша шектеулер	Ұпайлар
$0$	Мысалдар	$0$
$1$	$n \leq 20$	$8$
$2$	$k = 1$	$12$
$3$	$k \leq 3$	$17$
$4$	$n \leq 2000$	$15$
$5$	$n \leq 50000$	$16$
$6$	—	$32$

Мысалдар

Енгізу 1

Көшіру

3 2
aab
1 2 3

Жауап 1

Көшіру

Пікірлер

Қазіргі уақытта ешқандай пікір жоқ.