| Task: | String padding |
| Sender: | aalto26im_020 |
| Submission time: | 2026-11-02 17:15:33 +0200 |
| Language: | Python3 (PyPy3) |
| Status: | READY |
| Result: | ACCEPTED |
| test | verdict | time | |
|---|---|---|---|
| #1 | ACCEPTED | 0.05 s | details |
| #2 | ACCEPTED | 0.05 s | details |
| #3 | ACCEPTED | 0.05 s | details |
| #4 | ACCEPTED | 0.05 s | details |
| #5 | ACCEPTED | 0.05 s | details |
| #6 | ACCEPTED | 0.10 s | details |
| #7 | ACCEPTED | 0.13 s | details |
| #8 | ACCEPTED | 0.10 s | details |
| #9 | ACCEPTED | 0.12 s | details |
| #10 | ACCEPTED | 0.14 s | details |
| #11 | ACCEPTED | 0.04 s | details |
| #12 | ACCEPTED | 0.05 s | details |
| #13 | ACCEPTED | 0.04 s | details |
| #14 | ACCEPTED | 0.06 s | details |
| #15 | ACCEPTED | 0.06 s | details |
| #16 | ACCEPTED | 0.04 s | details |
| #17 | ACCEPTED | 0.04 s | details |
| #18 | ACCEPTED | 0.06 s | details |
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 |
