Chef vs Bharat Codechef solution. July Challenge 2021.

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

In the game, a positive integer N$N$ (in decimal system) is considered a "Chefora" if the number of digits d$d$ is odd and it satisfies the equation

N=∑i=0d−1Ni⋅10i,$$N=\sum _{i=0}^{d-1}{N}_i\cdot {10}^i,$$

where Ni$N_i$ is the i$i$-th digit of N$N$ from the left in 0$0$-based indexing.

Let Ai$A_i$ denote the i$i$-th smallest Chefora number.

They'll ask each other Q$Q$ questions, where each question contains two integers L$L$ and R$R$. The opponent then has to answer with

(∏i=L+1R(AL)Ai)mod109+7.$$(\prod _{i=L+1}^R(A_L{)}^{A_i})mod{10}^9+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 Q$Q$ - the number of questions Bharat asks.
• Each of the next Q$Q$ lines contains two integers L$L$ and R$R$.

Sample Input

2
1 2
9 11

Sample Output

1
541416750

Explanation

• For the first question:

  (A1)A2=12=1.$$(A_1{)}^{A_2}=1^2=1.$$

• For the second question:

  (A9)A10⋅(A9)A11=9101⋅9111≡541416750(mod109+7).

Python Code:

def chefora(arr):

    arr.append(-1)

    for i in range(1,100000+1):

        rem=i//10

        num=i

        while(rem>0):

            d=rem%10

            num=num*10+d

            rem=rem//10

        arr.append(num+arr[i-1])

        

arr=[]

chefora(arr)

Q=int(input())

for i in range(Q):

    L,R=map(int,input().split())

    Al=arr[L]-arr[L-1]

    A_sum=arr[R]-arr[L]

    res=1

    power=A_sum

    base=Al

    while power>0:

        if power%2==0:

            base=(base*base)%1000000007

            power=power//2

        else:

            res=(res*base)%1000000007

            power=power-1

    print(res%1000000007)

Another simplified solution:

(TLE in 2nd test case)

def nth_chefora(n):

    if n in range(1,10):

        return n

    return int(str(n)+str(n//10)[::-1])

for _ in range(int(input())):

    l,r=map(int,input().split())

    num=nth_chefora(l)

    sum_num=0

    for i in range(l+1,r+1):

        sum_num+=nth_chefora(i)

    res=pow(num,sum_num,(10**9+7))   

    print(res)