MOD1 = 10**9+7 MOD2 = 10**9+9 b1 = 9997 b2 = 12345 class RollingHash: def __init__(self, s): self.n = len(s) if type(s) == str: self.S = [ord(i) for i in s] else: self.S = s[:] self.hs1 = [0]*(self.n+1) self.hs2 = [0]*(self.n+1) self.pw1 = [1]*(len(s)+1) self.pw2 = [1]*(len(s)+1) for i in range(self.n): self.hs1[i+1] = (self.hs1[i]*b1 + self.S[i])%MOD1 self.hs2[i+1] = (self.hs2[i]*b2 + self.S[i])%MOD2 self.pw1[i+1] = self.pw1[i]*b1%MOD1 self.pw2[i+1] = self.pw2[i]*b2%MOD2 #部分文字列 [l,r)のハッシュをとる def get_hash1(self,l,r): return (self.hs1[r]-self.hs1[l]*self.pw1[r-l])%MOD1 def get_hash2(self,l,r): return (self.hs2[r]-self.hs2[l]*self.pw2[r-l])%MOD2 def issame(self,l1,r1,l2,r2): return self.get_hash1(l1,r1) == self.get_hash1(l2,r2) and self.get_hash2(l1,r1) == self.get_hash2(l2,r2) # 先頭何文字が同じ?その数を返す def same_prefix(self,l1,r1,l2,r2): ok = 0 ng = min(r1-l1,r2-l2) + 1 while ng-ok > 1: mid = (ok+ng)//2 if self.issame(l1,l1+mid,l2,l2+mid): ok = mid else: ng = mid return ok # 末尾何文字が同じ?その数を返す def same_suffix(self,l1,r1,l2,r2): ok = 0 ng = min(r1-l1,r2-l2) + 1 while ng-ok > 1: mid = (ok+ng)//2 if self.issame(r1-mid,r1,r2-mid,r2): ok = mid else: ng = mid return ok n,*s,m,x,d = open(0).read().split() n,x,d = int(n),int(x),int(d) R = [RollingHash(si) for si in s] def issame(i,j,mid): return R[i].get_hash1(0,mid) == R[j].get_hash1(0,mid) and R[i].get_hash2(0,mid) == R[j].get_hash2(0,mid) def same_prefix(i,j): ok = 0 ng = min(len(s[i]),len(s[j]))+1 while ng-ok > 1: mid = (ok+ng)//2 if issame(i,j,mid): ok = mid else: ng = mid return ok ans = 0 for _ in range(1,int(m)+1): i = x//(n-1) j = x%(n-1) if i>j: i,j = j,i else: j += 1 x = (x+d)%(n*(n-1)) ans += same_prefix(i,j) print(ans)