HackerRank Algebra – Sherlock and Square

Challenge: Sherlock and Square

Subdomeniu: Algebra (algebra)

Scor cont: 30.0 / 30

Submission status: Accepted

Submission score: 1.0

Submission ID: 464734347

Limbaj: cpp14

Link challenge: https://www.hackerrank.com/challenges/sherlock-and-square/problem

Cerinta

Watson gives a square of side length 1 to Sherlock. Now, after each second, each square of some arbitrary side $L$ will break into four squares each of side $L/2$(as shown in the image below). 

![img][123]

Now, Watson asks Sherlock: What will be the sum of length of solid lines after $N$ seconds?  

As the number can be large print result mod $(10^9 + 7)$.

For example, after 0 seconds, the length is 4.    
After 1 second, the length is 6.

**Input Format**    
First line contains $T$, the number of testcases. Each testcase contains $N$ in one line.   

**Output Format**

For each testcase, print the required answer in a new line. 

**Constraints**   
$1 \le T \le 10^5$    
$0 \le N \le 10^9$

**Sample input**

    3
    0
    1
    5
    
**Sample output**

    4
    6
    66

[123]: http://i.imgur.com/yXME9kL.png

Cod sursa

//sherlock-and-square.cpp
//Sherlock and Square
//Weekly Challenges - Week 11
//Author: derekhh

#include<iostream>
using namespace std;

const int MOD = 1000000007;

int ModExp(int a, int b, int n)
{
	long long c = 1, d = a;
	while (b)
	{
		if (b & 1) c = (c*d) % n;
		d = (d*d) % n;
		b >>= 1;
	}
	return (int)c;
}

int main()
{
	int t;
	cin >> t;
	while (t--)
	{
		int n;
		cin >> n;
		cout << (ModExp(2, n + 1, MOD) + 2) % MOD << endl;
	}
	return 0;
}