# Chef vs Bharat Solution | CHEFORA |CODECHEF JULY CHALLENGE

View problem on codechef

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 equationN=∑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

``````Join telegram channel for updates

CPP

#include <iostream>
#include<bits/stdc++.h>
using namespace std;
#define l1 long long
#define mod 1000000007

l1 power(l1 bs, l1 pw){
l1 res=1;
while(pw!=0){
if(pw%2==0){
bs=((bs%mod)*(bs%mod))%mod;
pw=floor(pw/2);
}
else{
res=((res%mod)*(bs%mod))%mod;
pw=pw-1;
}
}
return res;
}

l1 chefona(l1 num){
l1 chefnum=num;
l1 retnum=0;
if(num<10){
retnum=chefnum;
}
else if(num>=10){
num=num/10;
while(num!=0){
chefnum=chefnum*10+num%10;
num=num/10;
}
retnum=chefnum;
}
return retnum;
}

int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
l1 a={0};
l1 prearray={0};
for(l1 i=1;i<=100001;i++){
a[i]=chefona(i);
prearray[i]=prearray[i-1]+a[i];
}
l1 t;
cin>>t;
while(t--){
l1 l,r;
cin>>l>>r;
l1 diff=prearray[r]-prearray[l];
cout<<power(a[l],diff)<<"\n";

}
return 0;
}

Python

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))``````

1. 