[C++] [CSES] Bit Strings (Introductory Problems)

CSES의 아홉번째 문제입니다. 

크기가 n인 이진수는 몇가지로 표현할 수 있는지 알아내야 합니다.

 

Task

Your task is to calculate the number of bit strings of length n.

For example, if n=3, the correct answer is 8, because the possible bit strings are 000, 001, 010, 011, 100, 101, 110, and 111.

Input

The only input line has an integer n.

Output

Print the result modulo 1e9 + 7.

Constraints

• 1≤n≤1e6

Example

Input:
3

Output:
8

 

Code

#include<bits/stdc++.h>
using namespace std;
#define MOD 1000000007
typedef long long ll;

ll n;
ll go(ll n){
    if (n == 0) return 1;
    if (n == 1) return 2;
    ll cur = go(n / 2);
    cur = (cur * cur) % MOD;
    if (n % 2) cur = (cur * 2) % MOD;
    return cur;
}
int main(){
    cin >> n;
    cout << go(n);
}

생각해야 하는 것

• 2의 n제곱을 구하는 문제입니다.
• n의 제한이 1백만이기 때문에 for문 한번을 돌려도 시간초과가 나지 않지만, 분할정복을 통한다면 logN 의 시간복잡도로 구할 수 있습니다.
• 모듈러 연산의 특징을 이용하여 값을 잘 나눠주어야 합니다.
• cur * cur 을 구하는 과정에서 int 범위를 넘어갈 수 있기 때문에 long long으로 선언해줍니다.