Return to Answer

Having tested these functions, we can put it all together (using types that are guaranteed large enough to represent the expected range of values), getting something which is more efficient and easier to follow than the posted code:

(Note that this won't handle the full range of int correctly; it's enough for the subset of values we'll encounter in this problem. For a thorough implementation of an unbounded modular exponentiation, have a look at Modular exponentiation without range restriction here on Code Review.)

Having tested these functions (not shown here, to keep the answer reasonably short), we can put it all together (using types that are guaranteed large enough to represent the expected range of values), getting something which is more efficient and easier to follow than the posted code:

The obvious with this code is the lack of structure. There are two main computations, given that we've already spotted that we can add all the exponents and perform a single exponentiation with the sum:

The obvious issue with this code is the lack of structure. There are two main computations, given that we've already spotted that we can add all the exponents and perform a single exponentiation with the sum:

Having tested these functions, we can put it all together, getting something which is more efficient and easier to follow than the posted code:

#include <stdio.h>

const int result_modulus = 1000000007;

static long modexp(long base, int power, int modulus)
{
    long product = 1;
    while (power) {
        if (power % 2) {
            product = product * base % modulus;
        }
        base = base * base % modulus;
        power /= 2;
    }
    return product;
}

static int odd_palindrome(int n)
{
    int palindrome = n;
    while ((n /= 10)) {
        palindrome = palindrome * 10 + n % 10;
    }
    return palindrome;
}

static long compute_result(int left, int right)
{
    int sum = 0;
    for (int i = left + 1;  i <= right;  ++i) {
        sum += odd_palindrome(i);
    }
    return modexp(odd_palindrome(left), sum, result_modulus);
}

int main(void)
{
    int ntests;
    if (scanf("%d", &ntests) != 1) {
        return 1;
    }

    while (ntests --> 0) {
        int left, right;
        if (scanf("%d %d", &left, &right) != 2) {
            return 1;
        }
        printf("%ld\n", compute_result(left, right));
    }
}

Having tested these functions, we can put it all together (using types that are guaranteed large enough to represent the expected range of values), getting something which is more efficient and easier to follow than the posted code:

#include <inttypes.h>
#include <stdint.h>
#include <stdio.h>

typedef uint_fast32_t u32;
typedef uint_fast64_t u64;

const u32 result_modulus = 1000000007;

static u64 modexp(u64 base, u64 power, u32 modulus)
{
    u64 product = 1;
    while (power) {
        if (power % 2) {
            product = product * base % modulus;
        }
        base = base * base % modulus;
        power /= 2;
    }
    return product;
}

static u32 odd_palindrome(u32 n)
{
    u32 palindrome = n;
    while ((n /= 10)) {
        palindrome = palindrome * 10 + n % 10;
    }
    return palindrome;
}

static u64 compute_result(u32 left, u32 right)
{
    u64 sum = 0;
    for (u32 i = left + 1;  i <= right;  ++i) {
        sum += odd_palindrome(i);
    }
    return modexp(odd_palindrome(left), sum, result_modulus);
}

int main(void)
{
    int ntests;
    if (scanf("%d", &ntests) != 1) {
        return 1;
    }

    while (ntests --> 0) {
        u32 left, right;
        if (scanf("%"SCNuFAST32" %"SCNuFAST32, &left, &right) != 2) {
            return 1;
        }
        printf("%"PRIuFAST64"\n", compute_result(left, right));
    }
}