CodeEff/ECCO huggingface dataset:
# Original solution
from collections import defaultdict
import sys

S=sys.stdin.readline().strip()
l=len(S)

mod=10**9+7

dp=defaultdict(lambda: 0)   #dp[ (i,j) ]	i: nan-mojime,  j=0:All mojiretsu pattern , 1:A, 2:AB, 3:ABC
dp[(0,0)]=1

n=1
for i, s in enumerate(S):
	if s in "ABC":
		dp[ (i+1,0) ]=n
	elif s=="?":
		n*=3
		dp[ (i+1,0) ]=n		

nashi=0
a=1
ab=2
abc=3

for i,s in enumerate(S):
	if s =="A":
		dp[ (i+1,a) ]+=dp[ (i,nashi) ]
		dp[ (i+1,a) ]+=dp[ (i,a) ]
		dp[ (i+1,ab) ]+=dp[ (i,ab) ]
		dp[ (i+1,abc) ]+=dp[ (i,abc) ]
	elif s=="B":
		dp[ (i+1,ab) ]+=dp[ (i,ab) ]
		dp[ (i+1,ab) ]+=dp[ (i,a) ]
		dp[ (i+1,a) ]+=dp[ (i,a) ]
		dp[ (i+1,abc) ]+=dp[ (i,abc) ]
	elif s=="C":
		dp[ (i+1,abc) ]+=dp[ (i,abc) ]
		dp[ (i+1,abc) ]+=dp[ (i,ab) ]
		dp[ (i+1,a) ]+=dp[ (i,a) ]
		dp[ (i+1,ab) ]+=dp[ (i,ab) ]
	elif s=="?":
		dp[ (i+1,a) ]+=dp[ (i,a) ]*3
		dp[ (i+1,a) ]+=dp[ (i,nashi) ]
		dp[ (i+1,a) ]%=mod

		dp[ (i+1,ab) ]+=dp[ (i,ab) ]*3
		dp[ (i+1,ab) ]+=dp[ (i,a) ]	
		dp[ (i+1,ab) ]%=mod

		dp[ (i+1,abc) ]+=dp[ (i,abc) ]*3
		dp[ (i+1,abc) ]+=dp[ (i,ab) ]
		dp[ (i+1,abc) ]%=mod


print(( dp[(l,3)]%mod ))




# Optimized solution
S=input()
l=len(S)

mod=10**9+7

all_strings=1
a=0
ab=0
abc=0

for i,s in enumerate(S):
	if s =="A":
		a+=all_strings
	elif s=="B":
		ab+=a
	elif s=="C":
		abc+=ab
	elif s=="?":
		abc*=3
		abc+=ab
		ab*=3
		ab+=a
		a*=3
		a+=all_strings
	if s == "?":
		all_strings*=3

	all_strings%=mod
	a%=mod
	ab%=mod
	abc%=mod

print(abc)
# Original solution
# coding:utf-8

import sys


input = sys.stdin.readline
INF = float('inf')
MOD = 10 ** 9 + 7


def inpl(): return list(map(int, input().split()))


S = input().rstrip()

dp = [[0] * 4 for _ in range(len(S) + 1)]
dp[0][0] = 1
for i in range(len(S)):
    if S[i] == '?':
        dp[i + 1][0] = (dp[i][0] * 3) % MOD
        dp[i + 1][1] = (dp[i][1] * 3 + dp[i][0]) % MOD
        dp[i + 1][2] = (dp[i][2] * 3 + dp[i][1]) % MOD
        dp[i + 1][3] = (dp[i][3] * 3 + dp[i][2]) % MOD
    else:
        for j in range(4):
            dp[i + 1][j] = dp[i][j]

        if S[i] == 'A':
            dp[i + 1][1] = (dp[i + 1][1] + dp[i][0]) % MOD
        if S[i] == 'B':
            dp[i + 1][2] = (dp[i + 1][2] + dp[i][1]) % MOD
        if S[i] == 'C':
            dp[i + 1][3] = (dp[i + 1][3] + dp[i][2]) % MOD

print((dp[-1][-1]))


# Optimized solution
# coding:utf-8

import sys


input = sys.stdin.readline
INF = float('inf')
MOD = 10 ** 9 + 7


def inpl(): return list(map(int, input().split()))


S = input().rstrip()

na, a, ab, abc = 1, 0, 0, 0
for s in S:
    if s == 'A':
        a = (a + na) % MOD
    if s == 'B':
        ab = (ab + a) % MOD
    if s == 'C':
        abc = (abc + ab) % MOD
    if s == '?':
        # abc, ab, a, naの順で計算しないと値が上書きされる
        abc = (abc * 3 + ab) % MOD
        ab = (ab * 3 + a) % MOD
        a = (a * 3 + na) % MOD
        na = (na * 3) % MOD

print(abc)
# Original solution
#coding:utf-8
S=input()

all=1
a=ab=abc=0

for _ in range(len(S)):
    i=_+1
    c=S[_]
    if c=="A":
        a+=all
    if c=="B":
        ab+=a
    if c=="C":
        abc+=ab
    if c=="?":
        abc=abc*3+ab
        ab=ab*3+a
        a=a*3+all
        all*=3
print((abc%((10**9)+7)))

    














# Optimized solution
#coding:utf-8
S=input()

all=1
a=ab=abc=0
MOD=(10**9)+7
for _ in range(len(S)):
    i=_+1
    c=S[_]
    if c=="A":
        a+=all
    if c=="B":
        ab+=a
    if c=="C":
        abc+=ab
    if c=="?":
        abc=abc*3+ab
        ab=ab*3+a
        a=a*3+all
        all*=3
    a%=MOD
    ab%=MOD
    abc%=MOD
    all%=MOD
print((abc%((10**9)+7)))
# Original solution
import sys
readline = sys.stdin.readline

S = readline().rstrip()
DIV = 10 ** 9 + 7

dp = [[0] * 4 for i in range(len(S) + 1)]
# dp[i + 1][0] : i文字目まで見たとき、ABCの部分文字列がまだ始まっていない場合の数
# dp[i + 1][1] : i文字目まで見たとき、ABCのAまで一致した場合の数
# dp[i + 1][2] : i文字目まで見たとき、ABCのBまで一致した場合の数
# dp[i + 1][3] : i文字目まで見たとき、ABCのCまで一致した場合の数

dp[0][0] = 1

for i in range(len(S)):
  if S[i] == "A" or S[i] == "?":
    dp[i + 1][0] += dp[i][0] # まだ始まっていない状態をそのまま
    dp[i + 1][1] += dp[i][1] # まだ始まっていない状態をそのまま
    dp[i + 1][2] += dp[i][2] # まだ始まっていない状態をそのまま
    dp[i + 1][3] += dp[i][3] # まだ始まっていない状態をそのまま
    dp[i + 1][1] += dp[i][0] # 開始状態に遷移することが出来る
    
  if S[i] == "B" or S[i] == "?":
    dp[i + 1][0] += dp[i][0] # その文字を選ばない場合
    dp[i + 1][1] += dp[i][1] # その文字を選ばない場合
    dp[i + 1][2] += dp[i][2] # その文字を選ばない場合
    dp[i + 1][3] += dp[i][3] # その文字を選ばない場合
    dp[i + 1][2] += dp[i][1] # Bを使用した状態に遷移
  
  if S[i] == "C" or S[i] == "?":
    dp[i + 1][0] += dp[i][0] # その文字を選ばない場合
    dp[i + 1][1] += dp[i][1] # その文字を選ばない場合
    dp[i + 1][2] += dp[i][2] # その文字を選ばない場合
    dp[i + 1][3] += dp[i][3] # その文字を選ばない場合
    dp[i + 1][3] += dp[i][2] # Cを使用した状態に遷移
    
  for j in range(4):
    dp[i + 1][j] %= DIV
    
# 最後の文字まで見たとき、Cまで一致した場合の数が答え
print((dp[len(S)][3]))


# Optimized solution
import sys
readline = sys.stdin.readline

S = readline().rstrip()
DIV = 10 ** 9 + 7

dp = [[0] * 4 for i in range(len(S) + 1)]
# dp[i + 1][0] : i文字目まで見たとき、ABCの部分文字列がまだ始まっていない場合の数
# dp[i + 1][1] : i文字目まで見たとき、ABCのAまで一致した場合の数
# dp[i + 1][2] : i文字目まで見たとき、ABCのBまで一致した場合の数
# dp[i + 1][3] : i文字目まで見たとき、ABCのCまで一致した場合の数

dp[0][0] = 1

for i in range(len(S)):
  # 状態を遷移しない場合
  for j in range(4):
    dp[i + 1][j] += dp[i][j] * (3 if S[i] == "?" else 1) # ?の場合は全ての遷移があり得る
  
  if S[i] == "A" or S[i] == "?":
    dp[i + 1][1] += dp[i][0] # 開始状態に遷移することが出来る
    
  if S[i] == "B" or S[i] == "?":
    dp[i + 1][2] += dp[i][1] # Bを使用した状態に遷移
  
  if S[i] == "C" or S[i] == "?":
    dp[i + 1][3] += dp[i][2] # Cを使用した状態に遷移
    
  for j in range(4):
    dp[i + 1][j] %= DIV
    
# 最後の文字まで見たとき、Cまで一致した場合の数が答え
print((dp[len(S)][3]))
# Original solution
from heapq import*
def m():
 n=int(eval(input()))
 A=[]
 for _ in[0]*n:
  e=list(map(int,input().split()))
  A+=[list(zip(e[2::2],e[3::2]))]
 d=[0]+[float("inf")]*n
 H=[(0,0)]
 while H:
  u=heappop(H)[1]
  for v,c in A[u]:
   t=d[u]+c
   if d[v]>t:
    d[v]=t
    heappush(H,(t,v))
 print(('\n'.join(f'{i} {d[i]}'for i in range(n))))
m()


# Optimized solution
import sys
from heapq import*
def m():
 n=int(eval(input()))
 A=[]
 for e in sys.stdin:
  e=list(map(int,e.split()))
  A+=[list(zip(e[2::2],e[3::2]))]
 d=[0]+[float('inf')]*n
 H=[(0,0)]
 while H:
  u=heappop(H)[1]
  for v,c in A[u]:
   t=d[u]+c
   if d[v]>t:
    d[v]=t
    heappush(H,(t,v))
 print(('\n'.join(f'{i} {d[i]}'for i in range(n))))
m()
# Original solution
import sys
readline = sys.stdin.readline
from heapq import heapify, heappush, heappop
INF = float("inf")
def MAIN():
    n = int(eval(input()))
    adj = [[]] * n
    for _ in range(0, n):
        U = list(map(int, readline().split()))
        adj[U[0]] = list(zip(U[2::2], U[3::2]))
    def dijkstra():
        d = [0] + [INF] * (n - 1)
        hq = [(0, 0)]
        while hq:
            u = heappop(hq)[1]
            for v, c in adj[u]:
                alt = d[u] + c
                if d[v] > alt:
                    d[v] = alt
                    heappush(hq, (alt, v))
        print(("\n".join(f"{i} {c}" for i, c in enumerate(d))))
    dijkstra()
MAIN()



# Optimized solution
import sys
readline = sys.stdin.readline
from heapq import heapify, heappush, heappop
INF = float("inf")
def MAIN():
    n = int(eval(input()))
    adj = [[]] * n
    for _ in range(0, n):
        U = list(map(int, input().split()))
        adj[U[0]] = list(zip(U[2::2], U[3::2]))
    def dijkstra():
        d = [0] + [INF] * (n - 1)
        hq = [(0, 0)]
        while hq:
            u = heappop(hq)[1]
            for v, c in adj[u]:
                alt = d[u] + c
                if d[v] > alt:
                    d[v] = alt
                    heappush(hq, (alt, v))
        print(("\n".join(str(i) + " " + str(c) for i, c in enumerate(d))))
    dijkstra()
MAIN()
# Original solution
# -*- coding: utf-8 -*-
from heapq import heappop, heappush

N = int(eval(input()))
INF = float("inf")
adj = [[] for _ in range(N)]

for n in range(N):
    inp = tuple(map(int, input().split()))
    for i in range(inp[1]):
        adj[n] = list(zip(inp[2::2], inp[3::2]))


def dijkstra(adj):
    d = [INF for n in range(N)]
    d[0] = 0
    heap = [[0, 0]]
    while len(heap):
        pcost, p = heappop(heap)
    
        for v, c in adj[p]:
            new_cost = pcost + c
            if new_cost < d[v]:
                d[v] = new_cost
                heappush(heap, [new_cost, v])
    for n in range(N):
        print(("{} {}".format(n, d[n])))

dijkstra(adj)

# Optimized solution
# -*- coding: utf-8 -*-
from heapq import heapify, heappop, heappush
 
N = int(eval(input()))
INF = float("inf")
d = [INF for n in range(N)]
d[0] = 0
adj = [[] for _ in range(N)]
 
searched = [False for _ in range(N)]
searched[0] = True
 
for n in range(N):
    inp = tuple(map(int, input().split()))
    assert n == inp[0]
    adj[n] = list(zip(inp[2::2], inp[3::2]))
 
heap = [[0, 0]]
 
while len(heap):
    pcost, p = heappop(heap)
    searched[p] = True
     
    if d[p] < pcost:
        continue
     
    for v, c in adj[p]:
        if not searched[v]:
            new_cost = pcost + c
            if new_cost < d[v]:
                d[v] = new_cost
                heappush(heap, [new_cost, v])
 
for n in range(N):
    print(("{} {}".format(n, d[n])))
# Original solution
import heapq

INFTY = 100000000000000000000000000
heap = []
n = int(input())
graph = {}
for i in range(n):
    entry = list(map(int, input().split(' ')))
    u = entry[0]
    k = entry[1]
    graph[u] = {}
    for j in range(k):
        v = entry[2+j*2]
        c = entry[2+j*2+1]
        graph[u][v] = c

d = {}
visited = {}
heap = []
for i in range(n):
    d[i] = INFTY
    visited[i] = False

s = 0
d[s] = 0
visited[s] = True
heapq.heappush(heap,(0,s))

while len(heap) > 0:
    mincost,minnode = heapq.heappop(heap)
    if mincost > d[minnode]: continue
    visited[minnode] = True
    for i in graph[minnode]:
        if not visited[i] and d[i] > d[minnode] + graph[minnode][i]:
            d[i] = d[minnode] + graph[minnode][i]
            heapq.heappush(heap, (d[i],i))

for i in range(n):
    print(i,d[i])

# Optimized solution
from heapq import heappush, heappop

def dijkstra(G, s):
    n = len(G)
    fixed = set()
    d = {}
    for i in range(n):
        d[i] = 9999999999999999999999999999999999999
    d[s] = 0
    heap = [(0, s)]
    while len(fixed) < n:
        du, u = heappop(heap)
        for v in G[u]:
            if v in fixed:
                continue
            if du + G[u][v] < d[v]:
                d[v] = du + G[u][v]
                heappush(heap, (d[v], v))
        fixed.add(u)
    return d




n = int(input())
G = {}
for _ in range(n):
    entries = list(map(int, input().split(' ')))
    u = entries[0]
    k = entries[1]
    G[u] = {}
    for i in range(k):
        v = entries[i*2+2]
        c = entries[i*2+3]
        G[u][v] = c

d = dijkstra(G, 0)

for i in range(n):
    print(i, d[i])
# Original solution
import sys
    
global nodes
nodes = {}

def shortest_path(GRAPH):
    global nodes
    
    p1 = 0
    nodes[p1][1] = 0;

    edge={}
    total = 0
    mini = 0
    while True:
        nodes[p1][0]=True
        for p2 in range(len(nodes)):
            if nodes[p2][0]==False and (p1, p2) in GRAPH:
                tmp = nodes[p1][1] + GRAPH[(p1, p2)]
                if tmp < nodes[p2][1]:
                    nodes[p2][1] = tmp

        p1 = -1
        mini = 1000000
        for p2 in range(len(nodes)):
            if nodes[p2][0]==False and nodes[p2][1]<mini:
                p1 = p2
                mini = nodes[p2][1]
        if mini == 1000000:
            break
    return

def resultout():
    for i in range(len(nodes)):
        print("%d %d" %(i, nodes[i][1]))
    return

n = int(input())
x = {}
for i in range(n):
    seq = list(map(int,input().split()))
    i2 = seq.pop(0)
    n2 = seq.pop(0)
    for j in range(n2):
        j2 = seq.pop(0)
        weight = seq.pop(0)
        x[(i2, j2)] = weight
    nodes[i2] = [False, 1000000]

shortest_path(x)
resultout()

# Optimized solution
import sys
    
global distance

def shortest_path(GRAPH):
    global distance
    
    nodes2=list(range(len(distance)))
    p1 = 0
    distance[p1] = 0;

    while True:
        nodes2.remove(p1)
        for p2 in nodes2:
            if p2 in GRAPH[p1]:
                tmp = distance[p1] + GRAPH[p1][p2]
                if tmp < distance[p2]:
                    distance[p2] = tmp

        p1 = -1
        mini = 1000000
        for p2 in nodes2:
            if distance[p2]<mini:
                p1 = p2
                mini = distance[p2]
        if mini == 1000000:
            break
    return

def resultout():
    for i in range(len(distance)):
        print("%d %d" %(i, distance[i]))
    return

n = int(input())
x = [{} for i in range(n)]
distance = [1000000 for i in range(n)]

for i in range(n):
    seq = list(map(int,input().split()))
    i2 = seq.pop(0)
    n2 = seq.pop(0)
    for j in range(n2):
        j2 = seq.pop(0)
        weight = seq.pop(0)
        x[i2][j2] = weight

shortest_path(x)
resultout()
# Original solution
import sys
    
global distance

def shortest_path(GRAPH):
    global distance
    
    nodes2=list(range(len(distance)))
    p1 = 0
    distance[p1] = 0;

    while True:
        dp1 = distance[p1]
        gp1 = GRAPH[p1]
        nodes2.remove(p1)
        for p2 in nodes2:
            if p2 in gp1:
                tmp = gp1[p2] + dp1
                if tmp < distance[p2]:
                    distance[p2] = tmp

        p1 = -1
        mini = 1000000
        for p2 in nodes2:
            if distance[p2]<mini:
                p1 = p2
                mini = distance[p2]
        if mini == 1000000:
            break
    return

def resultout():
    for i in range(len(distance)):
        print("%d %d" %(i, distance[i]))
    return

n = int(input())
x = [{} for i in range(n)]
distance = [1000000 for i in range(n)]

for i in range(n):
    seq = list(map(int, input().split()))
    i2 = seq[0]
    tmp={}
    for j in range(2, len(seq), 2):
        j2,weight = seq[j:j+2]
        tmp[j2] = weight
    x[i2] = tmp

shortest_path(x)
resultout()

# Optimized solution
import sys
    
def shortest_path(GRAPH, distance):
    
    nodes0 = list(range(len(distance)))
    nodes1 = set()
    p1 = 0
    distance[p1] = 0
    while True:
        dp1 = distance[p1]
        gp1 = GRAPH[p1]
        status[p1]=2
        for p2 in list(gp1.keys()):
            tmp = gp1[p2] + dp1
            if status[p2]<=1 and tmp < distance[p2]:
                distance[p2] = tmp
                status[p2] = 1
                nodes1.add(p2)

        p1 = -1
        mini = 1000000
            
        for p2 in nodes1:
            if distance[p2]<mini:
                p1 = p2
                mini = distance[p2]
        if mini == 1000000:
            break
        nodes1.remove(p1)
    return

def resultout(distance):
    for i in range(len(distance)):
        print("%d %d" %(i, distance[i]))
    return

n = int(input())
x = [{} for i in range(n)]
status = [0 for i in range(n)]
distance = [1000000 for i in range(n)]

for i in range(n):
    seq = list(map(int, input().split()))
    tmp={}
    for j in range(2, len(seq), 2):
        j2, weight = seq[j:j+2]
        tmp[j2] = weight
    x[seq[0]] = tmp
    status[i] = 0

shortest_path(x, distance)
resultout(distance)
# Original solution
import sys
    
def shortest_path(GRAPH, distance):
    
    nodes0 = list(range(len(distance)))
    nodes1 = set()
    p1 = 0
    distance[p1] = 0
    while True:
        dp1 = distance[p1]
        gp1 = GRAPH[p1]
        status[p1]=2
        for p2 in list(gp1.keys()):
            tmp = gp1[p2] + dp1
            if status[p2]<=1 and tmp < distance[p2]:
                distance[p2] = tmp
                status[p2] = 1
                nodes1.add(p2)

        p1 = -1
        mini = 1000000
            
        for p2 in nodes1:
            if distance[p2]<mini:
                p1 = p2
                mini = distance[p2]
        if mini == 1000000:
            break
        nodes1.remove(p1)
    return

def resultout(distance):
    for i in range(len(distance)):
        print("%d %d" %(i, distance[i]))
    return

n = int(input())
x = [{} for i in range(n)]
status = [0 for i in range(n)]
distance = [1000000 for i in range(n)]

for i in range(n):
    seq = list(map(int, input().split()))
    tmp={}
    for j in range(2, len(seq), 2):
        j2, weight = seq[j:j+2]
        tmp[j2] = weight
    x[seq[0]] = tmp
    status[i] = 0

shortest_path(x, distance)
resultout(distance)

# Optimized solution
import sys
    
def shortest_path(GRAPH, distance):
    
    nodes = set()
    p1 = 0
    distance[p1] = 0

    while True:
        dp1 = distance[p1]
        gp1 = GRAPH[p1]
        status[p1]=1
        for p2 in list(gp1.keys()):
            tmp = gp1[p2] + dp1
            if status[p2]==0 and tmp < distance[p2]:
                distance[p2] = tmp
                nodes.add(p2)

        p1 = -1
        mini = 1000000
            
        for p2 in nodes:
            if distance[p2]<mini:
                p1 = p2
                mini = distance[p2]
        if mini == 1000000:
            break
        nodes.remove(p1)
    return

def resultout(distance):
    for i in range(len(distance)):
        print("%d %d" %(i, distance[i]))
    return

n = int(input())
x = [{} for i in range(n)]
status = [0 for i in range(n)]
distance = [1000000 for i in range(n)]

for i in range(n):
    seq = list(map(int, input().split()))
    tmp={}
    for j in range(2, len(seq), 2):
        j2, weight = seq[j:j+2]
        tmp[j2] = weight
    x[seq[0]] = tmp
    status[i] = 0

shortest_path(x, distance)
resultout(distance)
# Original solution
from collections import Counter, defaultdict, deque
import bisect
from sys import stdin, stdout
from itertools import repeat
import math
import random

# sys.stdin = open('input')

def inp():
    re = list(map(int, input().split()))
    if len(re) == 1:
        return re[0]
    return re

def inst():
    return input().strip()

def gcd(x, y):
   while(y):
       x, y = y, x % y
   return x

def my_main():
        n, k, c = inp()
        st = inst()
        front, end = [], []
        def get(now, ans):
            if len(ans) == k:
                return
            for i in range(now, n):
                if st[i]=='o':
                    ans.append(i+1)
                    return get(i+1+c, ans)
        get(0, front)
        st = st[::-1]
        get(0, end)
        for i in range(len(end)):
            end[i] = n-end[i]+1
        end.sort()
        if len(front)!=k or len(end)!=k:
            return
        ans = []
        # print front, end
        for i in range(k):
            if front[i] == end[i]:
                ans.append(front[i])
        if ans:
            print('\n'.join(map(str, ans)))

my_main()


# Optimized solution
from collections import Counter, defaultdict, deque
import bisect
from sys import stdin, stdout
from itertools import repeat
import math
import random

# sys.stdin = open('input')

def inp():
    re = list(map(int, input().split()))
    if len(re) == 1:
        return re[0]
    return re

def inst():
    return input().strip()

def gcd(x, y):
   while(y):
       x, y = y, x % y
   return x

def my_main():
        n, k, c = inp()
        st = inst()
        front, end = [], []
        def get(now, ans):
            while now < n:
                if len(ans) == k:
                    return
                for i in range(now, n):
                    if st[i]=='o':
                        ans.append(i+1)
                        now = i+c+1
                        break
                else:
                    break
        get(0, front)
        st = st[::-1]
        get(0, end)
        for i in range(len(end)):
            end[i] = n-end[i]+1
        end.sort()
        if len(front)!=k or len(end)!=k:
            return
        ans = []
        # print front, end
        for i in range(k):
            if front[i] == end[i]:
                ans.append(front[i])
        if ans:
            print('\n'.join(map(str, ans)))

my_main()
# Original solution
import sys
input = sys.stdin.readline


def inpl():
    return list(map(int, input().split()))


def GetBase(t=0):
    ret = []
    last = -C * 2 - 1
    for i, s in enumerate(S[t:]):
        if s == 'x':
            continue
        elif last + C >= i + t:
            continue

        ret.append(i + t)
        last = i + t
    return ret


def GetDepend(base_ans):
    ruiseki = []
    a = 0
    for s in S:
        if s == 'o':
            a += 1
            ruiseki.append(a)
        else:
            ruiseki.append(a)

    ret = {a: False for a in base_ans}
    for a in ret:
        if ruiseki[a] == ruiseki[min(N - 1, a + C)]:
            ret[a] = True
    return ret


def solve():
    base_ans = GetBase()
    if len(base_ans) > K:
        return []

    depend_dict = GetDepend(base_ans)
    for i, b in enumerate(base_ans):
        if depend_dict[b] is True:
            continue
        S[b] = 'x'
        tmp = GetBase(b)
        if len(tmp) + i < K:
            depend_dict[b] = True
        else:
            for s in set(tmp) - set(base_ans[i:]):
                depend_dict[s] = True

        S[b] = 'o'

    return [a + 1 for a in base_ans if depend_dict[a] is True]


N, K, C = inpl()
S = list(input().strip())

ans = solve()

for a in ans:
    print(a)


# Optimized solution
import sys
input = sys.stdin.readline


def inpl():
    return list(map(int, input().split()))


def GetBase(t=0):
    ret = []
    last = -C * 2 - 1
    for i, s in enumerate(S[t:]):
        if s == 'x':
            continue
        elif last + C >= i + t:
            continue

        ret.append(i + t)
        last = i + t
    return ret


def GetReverse():
    ret = []
    last = -C * 2 - 1
    for i, s in enumerate(S[::-1]):
        if s == 'x':
            continue
        elif last + C >= i:
            continue

        ret.append(len(S) - 1 - i)
        last = i
    return reversed(ret)


def GetDepend(base_ans):
    ruiseki = []
    a = 0
    for s in S:
        if s == 'o':
            a += 1
            ruiseki.append(a)
        else:
            ruiseki.append(a)

    ret = {a: False for a in base_ans}
    for a in ret:
        if ruiseki[a] == ruiseki[min(N - 1, a + C)]:
            ret[a] = True
    return ret


def solve():
    base_ans = GetBase()
    if len(base_ans) > K:
        return []

    reverse_ans = GetReverse()

    return sorted(list(set(base_ans) & set(reverse_ans)))


N, K, C = inpl()
S = list(input().strip())

ans = solve()

for a in ans:
    print((a + 1))
# Original solution
N,K,C=map(int,input().split())
S=input()
i=0
d1=[-1]*N
for k in range(K):
    try:
        i+=S[i:].index('o')
    except:
        break
    d1[i]=k
    i+=C+1
i=0
d2=[-1]*N
for k in range(K-1,-1,-1):
    try:
        i+=S[N-1-i::-1].index('o')
    except:
        break
    d2[N-1-i]=k
    i+=C+1
print(*[i+1 for i in range(N) if d1[i]==d2[i]>=0],sep='\n')


# Optimized solution
N,K,C=map(int,input().split())
S=input()
i=0
d1=[-1]*N
for k in range(K):
    while S[i]=='x' and i<N:
        i+=1
    if i==N:break
    d1[i]=k
    i+=C+1
i=0
d2=[-1]*N
for k in range(K-1,-1,-1):
    while S[N-1-i]=='x' and i<N:
        i+=1
    if i==N:break
    d2[N-1-i]=k
    i+=C+1
print(*[i+1 for i in range(N) if d1[i]==d2[i]>=0],sep='\n')