Submission details
Task:String padding
Sender:aalto26im_020
Submission time:2026-11-02 17:15:33 +0200
Language:Python3 (PyPy3)
Status:READY
Result:ACCEPTED
Test results
testverdicttime
#1ACCEPTED0.05 sdetails
#2ACCEPTED0.05 sdetails
#3ACCEPTED0.05 sdetails
#4ACCEPTED0.05 sdetails
#5ACCEPTED0.05 sdetails
#6ACCEPTED0.10 sdetails
#7ACCEPTED0.13 sdetails
#8ACCEPTED0.10 sdetails
#9ACCEPTED0.12 sdetails
#10ACCEPTED0.14 sdetails
#11ACCEPTED0.04 sdetails
#12ACCEPTED0.05 sdetails
#13ACCEPTED0.04 sdetails
#14ACCEPTED0.06 sdetails
#15ACCEPTED0.06 sdetails
#16ACCEPTED0.04 sdetails
#17ACCEPTED0.04 sdetails
#18ACCEPTED0.06 sdetails

Code

import sys
def main():
    input_data=sys.stdin.read().split()
    n=int(input_data[0])
    s=input_data[1]
    m=len(s)
    MOD=10**9+7

    pi=[0]*m #prefix/fallback
    for i in range(1,m):
        k=pi[i-1]
        while k>0 and s[i]!=s[k]:
            k=pi[k-1]
        if s[i]==s[k]:
            k+=1
        pi[i]=k
#dono side ka PnC x 26 for each char
    next_state=[[0]*26 for _ in range(m)]
    for j in range(m):
        for c in range(26):
            ch=chr(ord('A')+c)
            k=j
            while k>0 and s[k]!=ch:
                k=pi[k-1]
            if s[k]==ch:
                k+=1
            next_state[j][c]=k #can start now

    dp=[0]*m
    dp[0]=1
    valid=0
    for i in range(n):
        next_dp=[0]*m
        next_valid=(valid*26)%MOD #already has s, so rest x26

        for j in range(m):
            if dp[j]==0:
                continue
            
            for c in range(26):
                nj=next_state[j][c]
                if nj==m:
                    next_valid=(next_valid+dp[j])%MOD
                else:
                    next_dp[nj]=(next_dp[nj]+dp[j])%MOD
        
        dp=next_dp
        valid=next_valid
    print(valid)

main()

Test details

Test 1

Verdict: ACCEPTED

input
100
YWANYWAZYWANYWA

correct output
134837038

user output
134837038

Test 2

Verdict: ACCEPTED

input
100
EDMXEDVNEDMXED

correct output
642715950

user output
642715950

Test 3

Verdict: ACCEPTED

input
100
SDARSDAWVSDARSDA

correct output
748728234

user output
748728234

Test 4

Verdict: ACCEPTED

input
100
HBDHBSHBDHB

correct output
594110560

user output
594110560

Test 5

Verdict: ACCEPTED

input
100
CUNXUYGNGNEROXVLASQB

correct output
675706202

user output
675706202

Test 6

Verdict: ACCEPTED

input
1000
LZAOLRKGLZAOLXLZAOLRKGLZAOLTLZ...

correct output
318756627

user output
318756627

Test 7

Verdict: ACCEPTED

input
1000
SUASJSUASSGDSUASJSUASGKSUASJSU...

correct output
367950233

user output
367950233

Test 8

Verdict: ACCEPTED

input
1000
NHYGNHEWNHYGNHFSNHYGNHEWNHYGNH...

correct output
849646061

user output
849646061

Test 9

Verdict: ACCEPTED

input
1000
ZOCUZOCGRFZOCUZOCOQZOCUZOCGRFZ...

correct output
32142571

user output
32142571

Test 10

Verdict: ACCEPTED

input
1000
LJZMKDTECKBXBTQQUMLGADBDNGWGPY...

correct output
26128120

user output
26128120

Test 11

Verdict: ACCEPTED

input
1
A

correct output
1

user output
1

Test 12

Verdict: ACCEPTED

input
100
AVXETIDRHKPAKRBEAAVHLOPFACULSE...

correct output
228794815

user output
228794815

Test 13

Verdict: ACCEPTED

input
3
ABC

correct output
1

user output
1

Test 14

Verdict: ACCEPTED

input
745
RRQOVUJRQBIMIQK

correct output
504765084

user output
504765084

Test 15

Verdict: ACCEPTED

input
666
ABCABCDABCABCX

correct output
920654188

user output
920654188

Test 16

Verdict: ACCEPTED

input
6
AA

correct output
2212651

user output
2212651

Test 17

Verdict: ACCEPTED

input
1
B

correct output
1

user output
1

Test 18

Verdict: ACCEPTED

input
1000
OMAKARAAA

correct output
408042378

user output
408042378