# Chef vs Bharat Codechef Solution

Page Contents

## Chef vs Bharat Codechef Solution

Chef and his friend Bharat have decided to play the game “The Chefora Spell”.

In the game, a positive integer NN (in decimal system) is considered a “Chefora” if the number of digits dd is odd and it satisfies the equation

N=∑i=0d−1Ni⋅10i,N=∑i=0d−1Ni⋅10i,

where NiNi is the ii-th digit of NN from the left in 00-based indexing.

Let AiAi denote the ii-th largest Chefora number.

They’ll ask each other QQ questions, where each question contains two integers LL and RR. The opponent then has to answer with(∏i=L+1R(AL)Ai)mod109+7.(∏i=L+1R(AL)Ai)mod109+7.

Bharat has answered all the questions right, and now it is Chef’s turn. But since Chef fears that he could get some questions wrong, you have come to his rescue!

### Input

• The first line contains an integer QQ – the number of questions Bharat asks.
• Each of the next QQ lines contains two integers LL and RR.

### Output

Print QQ integers – the answers to the questions on separate lines.

### Constraints

• 1≤N,Q≤1051≤N,Q≤105
• 1≤L<R≤N1≤L<R≤N

Subtask #2 (70 points): Original constraints

### Sample Input

``````2
1 2
9 11
``````

### Sample Output

``````1
541416750
``````

### Explanation

• For the first question:(A1)A2=12=1.(A1)A2=12=1.
• For the second question:(A9)A10⋅(A9)A11=9101⋅9111≡541416750(mod109+7).

## Solution

Program Python:

``````Credit : here
class palinpsum:
def __init__(self, n):
self.n = n
self.i = 0
self.palindromes = *n
self.prefixSums = *n

self.palindromes[self.i] = val
self.prefixSums[self.i] = val
if self.i != 0:
self.prefixSums[self.i] += self.prefixSums[self.i-1]
self.i = self.i+1

def isFull(self):
return self.i == self.n

def prefixsum(self, L, R):
return self.prefixSums[R]-self.prefixSums[L]

def getFirstPalin(self, index):
return self.palindromes[index]

def oddpalin(inp):
n = inp
palin = inp
n = n//10
while n > 0:
palin = palin*10+(n%10)
n = n//10
return palin;

def gpalin(palinpsum):
i = 1
while not palinpsum.isFull():
i = i+1

def formula(L, R, palinpsum):
power = palinpsum.prefixsum(L-1, R-1);
base = palinpsum.getFirstPalin(L-1);
return pow(base, power, 1000000007);

palinpsum = palinpsum(100001)
gpalin(palinpsum)
q = int(input())
while q > 0:
q = q-1
L,R=map(int,input().split())
print(formula(L, R, palinpsum))``````

Program Python:

``````
Credit: here

def findpower(base,power):
mod = 10**9+7
res = 1
while power!=0:
if power%2==0:
base = ((base%mod)*(base%mod))%mod
power = power//2
else:
res = ((res%mod)*(base%mod))%mod
power = power-1
return res

def findshefola(num):
palin = num
num = num//10
while num>0:
palin = palin*10+num%10
num = num//10
return palin

arr = *(10**5+1)
arrsm = *(10**5+1)
for i in range(1,10**5+1):
arr[i] = findshefola(i)
arrsm[i] = arrsm[i-1] + arr[i]

for _ in range(int(input())):
l,r = map(int,input().split())
power = arrsm[r]-arrsm[l]
print(findpower(arr[l],power))``````