Forget about code (until the very end) and just consider how you could generate a sorted list of palindromes (of odd length) "by hand".
The first (1-digit) palindromes are 0, 1, ..., 9 i.e. the palindrome at position n (0 ≤ n < 10) in the list is n.
After that come 101, 111, 121, ..., but finding them by hand gets tedious (especially since the list is infinite), so it's time to look for a pattern.
In general, any palindrome consisting or more than 1 digit is of the form
a ++ d ++ rev a, where
a is a positive number,
d is a digit,
rev a is the reversal of
++ means concatenation.
The smallest palindrome larger than
a ++ d ++ rev a is:
a ++ (d+1) ++ rev a, if d < 9
(a+1) ++ 0 ++ rev (a+1), if d = 9
Ignoring the reversed part this is just the algorithm for "adding 1". The palindrome at position n (n ≥ 10) in the list is therefore
(n div 10) ++ (n mod 10) ++ rev (n div 10), where
div is integer division and
mod is the remainder-function.
Collecting and cleaning gives the following formula for palindrome Pₙ₊₁ at position n (the "+1" is just there to make P₁ the first and not the second palindrome):
n, if 0 ≤ n < 10
n ++ rev (n div 10), if n ≥ 10
This is where I stopped in my previous answer: according to the title the question is how to compute Pₙ, and the formula above surely is trivial enough be translated into code without much thought.
The description, however, poses a different question, i.e. not how to compute Pₙ, but how to compute the product of the terms Pₙ^Pₓ (n < x ≤ k) fast. I decided to retract my answer until I had time to answer that one. Now, let's continue...
For the modular residues (10⁹ + 7) any integer type supporting at least 29 bits suffices (and the size of any Pₙ is even less than that at 23 bits, assuming n ≤ 5000). The product of two 29-bits numbers fits in 58 bits, so as long as you're not tardy in replacing intermediate results by their modular residues a typical 64 bit integer type will do.
Computing a single Pₙ takes O(log(n)) time since rev and ++ are linear in the number of digits and the other operations are usually assumed to be O(1). So computing all of the palindromes involved in the expression takes O((n-k) log k). Modular exponentiation takes logarithmic time (unless implemented naively), so computing the terms Pₙ^Pₓ (n < x ≤ k) takes O(log Pₓ) = O(log x) = O(log k) per term, or O((n-k) log k) in total. Modular multiplication of the k-n terms takes O(k-n). Putting it all together the overall performance is O((n-k) log k). n and k and the hidden constants in O() are small so this is fast.
The implementation is straightforward and doesn't need any optimization hacks. The bottleneck is probably the rev function as I reckon that it's not built in natively. At the cost of more complexity and O(n+k) memory you could get rev down to O(1) amortized, but it's not worth the effort.
PS: According to the context description the inputs to the problem are T, L and R which don't occur in the problem statement (!) (I can guess what they mean, just like I can guess what your real question is, but I shouldn't have to).
Addendum: I couldn't resist mentioning the following performance tweak:
For 0 ≤ m and 0 ≤ p < 10, P₁₀ₘ₊ₚ = m ++ p ++ rev m (define P₀ = 0 to make this true).
Hence the sum P₁₀ₘ + ... + P₁₀ₘ₊ₚ = (p+1)*P₁₀ₘ + ½×p×(p-1)×10^(number of digits of m)
That means that if n=82 and k=3719 you don't need to explicitly compute and sum 3638 palindromes to determine P₈₂ + … + P₃₇₁₉. Instead it suffices to compute P₈₀, P₉₀, …, P₃₇₁₀, which are just 364 palindromes.
The formula above essentially handles the missing bits (extra in case of P₈₀) and they can be computed in one go per computed P₁₀ₘ.
The final step is to raise Pₙ to the sum.
I expect this makes the overall computation up to 10 times faster than the original computation.