# PROBLEM LINK:

**Author :** Mayuresh Patle

**Testers :** Jaymeet Mehta, Smit Mandavia, Taranpreet Singh

**Editorialist :** Mayuresh Patle

# DIFFICULTY:

EASY

# PREREQUISITES:

Basic Combinatorics, Probability, Modular Multiplicative Inverse

# PROBLEM:

Given the length L_i of string which may contain both uppercase and lowercase English alphabets, find the probability that this string will be a palindrome, under the condition that for exactly K (0 \leq K \leq 26) alphabets, their uppercase and lowercase representations are treated to be similar.

This probability can be represented as P/Q where P and Q are integers. Thus, print the result as P.Q^{-1} \mod 10^9+7, where Q^{−1} denotes the modular multiplicative inverse of Q(modulo (10^9+7)).

# EXPLANATION:

Considering all 52 (uppercase and lowercase) characters, it can be proved that the total number of strings of length L will be 52^L, since each one of the L positions in the string can be occupied by any of the available 52 characters.

For any string S of length L to be a palindrome, S[i]=S[L-i] must be satisfied, \forall i \in [1,L]. Thus for every pair of indices (i,L-i), we need similar characters at both indices.

- Here, the order of indices in pairs do not matter, i.e. (i,L-i) will be same as (L-i,i).
- Also, for odd L this condition will always hold true for center element ( i.e. for (\frac{L}{2}, \frac{L}{2})).

Thus we have total \lfloor \frac{L}{2} \rfloor such pairs to deal with.

## For K=0:

If K=0, then for each pair we need to have exactly same character at both the indices.

Since we can choose any of the 52 characters for any of the {\lfloor\frac{L}{2}\rfloor} pairs, total number of palindromes will be 52^ {\lfloor\frac{L}{2}\rfloor} in this case.

Hence, in this case, the numerator will be 52^ {\lfloor\frac{L}{2}\rfloor} and denominator will be 52^L, after performing division ,we get P = 1 and Q = 52^{\lceil\frac{L}{2}\rceil}

## For 0 \leq K \leq 26:

In this case, each pair can be:

- (uppercase,uppercase) for any character, i.e. total 26 pairs.
- (lowercase,lowercase) for any character, i.e. total 26 pairs.
- (uppercase,lowercase) for any of the K characters, i.e. total K pairs.
- (lowercase,uppercase) for any of the K characters, i.e. total K pairs.

Considering all these possibilities, we have total (26 + 26 + K + K) = (52+2*K) possibilities for every single pair.

Thus, total number of palindromes will be:

- (52 + 2*K)^{\lfloor \frac{L}{2} \rfloor} if L is even.
- 52*(52 + 2*K)^{\lfloor \frac{L}{2} \rfloor} if L is odd, since we can have any of the 52 characters at the center.

Hence, numerator=(52 + 2*K)^{\lfloor \frac{L}{2} \rfloor} and denominator=52^{L - (L \mod 2)}, since 52 will be canceled out from numerator and denominator for odd L.

Since complete division is concerned, the result will be same even if P and Q are not co-primes. Thus, P=numerator and Q=denominator.

Since m = (10^9+7) is prime, we can use Fermats’s little theorem to calculate P . Q^{-1} \mod m.

Hence, Q^{-1} \mod m \equiv Q^{m-2} \mod m.

Therefore, the required probability will be (P * (Q ^ {m-2} \mod m)) \mod m.

**Time Complexity :** O( \log m) for each string.

# SOLUTION:

## Setter's Solution

```
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define modinv(n,m) modex(n,m-2,m)
#define moddiv(n,d,m) (n*modinv(d,m))%m
const ll mod=1e9+7;
ll modex(ll x,ll p,ll m)
{
ll ans=1;
x=x%m;
while(p>0)
{
if(p&1) ans=(ans*x)%m;
p=p>>1;
x=(x*x)%m;
}
return ans;
}
int main()
{
ll T,n,k,l,nr,dr;
cin>>T;
while(T--)
{
cin>>n>>k;
k<<=1;
while(n--)
{
cin>>l;
nr=modex(52+k,l>>1,mod);
dr=modex(52,l-(l&1),mod);
cout<<moddiv(nr,dr,mod)<<endl;
}
}
return 0;
}
```