s = raw_input()
q = input()
def combination(n, d):
k = d - 2
result = 1
for i in range(k):
result*=n
n-=1
for i in range(k):
result/=k
k-=1
return result
def mod(num):
return num % (10**9+7)
arr = []
for i in range(q):
d, xy = raw_input().split()
d = int(d)
x = xy[0]
y = xy[1]
arr_l = []
arr_c = []
a = -1
b = -1
if x != y:
for i in range(len(s)):
if i >= d - 2 and s[i] == x:
arr_l.append(i)
arr_c.append(0)
a = i
b += 1
elif len(arr_l)>0 and s[i]==y and i > a:
for k in range(len(arr_c)):
arr_c[k] += 1
for j in range(len(arr_l)):
arr_l[j] = mod(combination(arr_l[j], d))
total = 0
for i in range(len(arr_l)):
total += mod(arr_l[i]*arr_c[i])
arr.append(total)
else:
for i in range(len(s)):
if i >= d - 2 and s[i] == x:
arr_l.append(i)
for k in range(len(arr_c)):
arr_c[k] += 1
arr_c.append(0)
for j in range(len(arr_l)):
arr_l[j] = mod(combination(arr_l[j], d))
total = 0
for i in range(len(arr_l)):
total += mod(arr_l[i]*arr_c[i])
arr.append(total)
for i in arr:
print i
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
336 ms |
20168 KB |
Output is correct |
| 2 |
Incorrect |
296 ms |
20168 KB |
Output isn't correct |
| 3 |
Incorrect |
318 ms |
20168 KB |
Output isn't correct |
| 4 |
Incorrect |
337 ms |
20344 KB |
Output isn't correct |
| 5 |
Execution timed out |
2064 ms |
20344 KB |
Time limit exceeded |
| 6 |
Execution timed out |
2061 ms |
20984 KB |
Time limit exceeded |
| 7 |
Execution timed out |
2058 ms |
21288 KB |
Time limit exceeded |
| 8 |
Execution timed out |
2048 ms |
21288 KB |
Time limit exceeded |
| 9 |
Execution timed out |
2053 ms |
21288 KB |
Time limit exceeded |
| 10 |
Execution timed out |
2071 ms |
21288 KB |
Time limit exceeded |
