There was one question here is the link

Rohan loves Palindromes. Palindrome is a string that read same forward and backward. For example abba is a palindrome while abca is not.

Rohan is forming a palindrome of length lesser than or equal to n, with first k characters of lowercase English letters. He needs your help to find out the number of possible palindromes.

Output the result modulo 10⁹ + 7

Input Format: First line contains 2 space separated integers, n and k

Output Format: Output a single integer, which is answer to the problem

Constraints: 1 ≤ n ≤ 10⁹        1 ≤ k ≤ 26

Sample input:

3 2

Sample Output:

8

I tried making it and it was working fine for some small input but in case of large input its saying time limit exceeded. I think my code running time is O(n²), but I am not sure.

###My code:

a,b = raw_input().split()
a = int(a)
b = int(b)
sum = 0
z = b
for i in xrange(1,a+1,2):
    d = z*2
    sum +=d
    z = z*b

if (a+1) % 2 == 0:
    sum = sum - (d/2)
print sum%1000000007

I am interested in knowing that where I am doing wrong with my code and how can I fix this. Also what should I do at first when I face these kind of problem whenever I have to deal with long input because everytime I see any time limit error I am not able to fix it.

Here is the problem description from hackerearth.com:

Rohan loves Palindromes. Palindrome is a string that read same forward and backward. For example abba is a palindrome while abca is not.

Rohan is forming a palindrome of length lesser than or equal to \$n\$, with first \$k\$ characters of lowercase English letters. He needs your help to find out the number of possible palindromes.

Output the result modulo \$10^9 + 7\$

Input Format: First line contains 2 space separated integers, \$n\$ and \$k\$

Output Format: Output a single integer, which is answer to the problem

Constraints: \$1 ≤ n ≤ 10^9\$        \$1 ≤ k ≤ 26\$

Sample input:

3 2

Sample Output:

8

I tried making it and it was working fine for some small input but in case of large input its saying time limit exceeded. I think my code running time is \$O(n^2)\$, but I am not sure.

###My code:

a,b = raw_input().split()
a = int(a)
b = int(b)
sum = 0
z = b
for i in xrange(1,a+1,2):
    d = z*2
    sum +=d
    z = z*b

if (a+1) % 2 == 0:
    sum = sum - (d/2)
print sum%1000000007

I am interested in knowing that where I am doing wrong with my code and how can I fix this. Also what should I do at first when I face these kind of problem whenever I have to deal with long input because every time I see any time limit error I am not able to fix it.

There was one question here is the link

Rohan loves Palindromes. Palindrome is a string that read same forward and backward. For example abba is a palindrome while abca is not.

Rohan is forming a palindrome of length lesser than or equal to n, with first k characters of lowercase English letters. He needs your help to find out the number of possible palindromes.

Output the result modulo 109 + 7

Input Format First line contains 2 space separated integers, n and k

Output Format Output a single integer, which is answer to the problem

Constraints 1 ≤ n ≤ 109 1 ≤ k ≤ 26

Sample input:

3 2

Sample Output:

8

I tried making it and it was working fine for some small input but in case of large input its saying time limit exceeded. According to me my code running time is O(n^2) (I am not sure)

###My code:

a,b = raw_input().split()
a = int(a)
b = int(b)
sum = 0
z = b
for i in xrange(1,a+1,2):
    d = z*2
    sum +=d
    z = z*b

if (a+1) % 2 == 0:
    sum = sum - (d/2)
print sum%1000000007

I am interested in knowing that where I am doing wrong with my code and how can I fix this. Also what should I do at first when I face these kind of problem whenever I have to deal with long input because everytime I see any time limit error I am not able to fix it.

There was one question here is the link

Rohan loves Palindromes. Palindrome is a string that read same forward and backward. For example abba is a palindrome while abca is not.

Rohan is forming a palindrome of length lesser than or equal to n, with first k characters of lowercase English letters. He needs your help to find out the number of possible palindromes.

Output the result modulo 10⁹ + 7

Input Format: First line contains 2 space separated integers, n and k

Output Format: Output a single integer, which is answer to the problem

Constraints: 1 ≤ n ≤ 10⁹        1 ≤ k ≤ 26

Sample input:

3 2

Sample Output:

8

I tried making it and it was working fine for some small input but in case of large input its saying time limit exceeded. I think my code running time is O(n²), but I am not sure.

###My code:

a,b = raw_input().split()
a = int(a)
b = int(b)
sum = 0
z = b
for i in xrange(1,a+1,2):
    d = z*2
    sum +=d
    z = z*b

if (a+1) % 2 == 0:
    sum = sum - (d/2)
print sum%1000000007

I am interested in knowing that where I am doing wrong with my code and how can I fix this. Also what should I do at first when I face these kind of problem whenever I have to deal with long input because everytime I see any time limit error I am not able to fix it.