# [Silver II] Candy [문제 링크](https://www.acmicpc.net/problem/12897) ## 문제 설명 <p>영희는 지난주에 철수의 생일 선물로 서로 다른 맛의 사탕 N개를 준비했습니다. 사탕은 맛에 따라 1번부터 N번까지의 사탕이 있다고 하겠습니다. 사탕들을 모두 상자에 담아서 정성스럽게 포장을 하여 철수에게 전해주기로 하였습니다.</p> <p>철수의 생일 날이 되었습니다. 영희는 준비해두었던 사탕 꾸러미를 철수에게 주었습니다. 그런데 철수는 꾸러미에서 이상한 점을 발견했습니다. 이미 포장이 뜯어져 있던 것입니다. 철수는 영희에게 원래 받았어야 할 사탕의 개수 N에 대해 전해 들었고, 사탕이 몇 개 사라졌을 수도 있겠다는 생각이 들었습니다. 사탕은 하나도 사라지지 않았을 수 있고, 전부 다 사라졌을 수도 있습니다.</p> <p>철수는 K(1≤K≤N)개의 사탕을 받으면 총 2^K만큼의 만족도를 느낀다고 합니다. 예를 들어, 철수가 1번, 3번, 4번 총 3개의 사탕을 선물 받았다면, 2³만큼의 만족도를 느끼게 되는 것입니다. 단, 철수가 사탕을 하나도 못 받는 경우에는 철수는 0의 만족도를 느낍니다.</p> <p>이때, 철수는 본인이 얻을 수 있는 가능한 모든 경우의 수의 만족도 합이 궁금해졌습니다. 철수의 궁금증을 해결해주는 프로그램을 작성하세요.</p> ## 입력 <p>입력의 첫째 줄에는 서로 다른 사탕의 개수를 나타내는 N(2 ≤ N ≤ 100,000)가 주어집니다.</p> ## 출력 <p>첫째 줄에 철수가 느낄 수 있는 모든 만족도의 합을 1,000,000,007로 나눈 나머지를 출력합니다.</p> ## 풀이 ∑i=1, i<=n (nCi * 2^i)를 구하는 문제입니다. (a+b)^n = ∑i=0, i<=n (nCi * a^(n-i) * b^i) 이러한 이항 정리 식의 a와 b에 각각 1과 2를 넣어 해결할 수 있습니다. ``` c++ #include<bits/stdc++.h> using namespace std; typedef long long ll; const ll MOD = 1'000'000'007; int main() { ios::sync_with_stdio(0); cin.tie(0); int n; cin >> n; ll res=1; while(n--) res = res*3%MOD; cout << res-1; } ```