Ositus

def Halve(s):
    
    return s[:len(s)//2],s[len(s)//2:]
def noOverlaps(a,b):
    for i in range(len(a)):
        if b.find(a[i])!=-1:
            return False
    return True

def Partition(s:str):
    if len(s)==1:
        return {(s,s):1,("",s):1}
    a0,b0 = Halve(s)
    a=Partition(a0)
    b=Partition(b0)
    out={}
    for i in a.keys():
        for j in b.keys():
            if noOverlaps(i[1],j[0]):
                if i[0]==i[1]:
                    x = i[0]+j[0]
                else:
                    x = i[0]
                if j[0]==j[1]:
                    y = i[1]+j[1]
                else:
                    y = j[1]
                out.setdefault((x,y),0)
                out[(x,y)]+=a[i]*b[j]
    return out

def Total(d):
    out=0
    for i in d.keys():
        if i[0]!='':
            out+=d[i]
    return out
        
    

I=input()

out1 =Partition(I)

#print(out1)
print(Total(out1)%(10**9+7))

Test 1

Group: 1, 2, 3

Verdict: ACCEPTED

Test 2

Group: 1, 2, 3

Verdict: ACCEPTED

Test 3

Group: 1, 2, 3

Verdict: WRONG ANSWER

Test 4

Group: 1, 2, 3

Verdict: ACCEPTED

Test 5

Group: 2, 3

Verdict: WRONG ANSWER

Test 6

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 7

Group: 3

Verdict: TIME LIMIT EXCEEDED