<|instruction|>
Solve the below problem. The solution should start with an abridged problem statement. Then key observations. Then full solution based on the observations. Then C++ and Python implementations with comments.

374. Save Vasya
Time limit per test: 0.25 second(s)
Memory limit: 65536 kilobytes
input: standard
output: standard



Vasya has huge problems. He needs to take polynomial ax + b, then calculate its k-th power and evaluate the sum of its coefficients. Your task is to help him.

Input
The first line of the input contains three integers a, b and k (1 ≤ a, b≤ 100, 1≤ k≤ 20).

Output
The first line must contain the sum of coefficients of the resulting polynomial.

Example(s)
sample input
sample output
1 2 2

<|response|>
1. Abridged Problem Statement  
   Given integers a, b and k, consider the polynomial P(x) = a·x + b. Compute P(x)^k and output the sum of its coefficients.

2. Key Observations  
   - For any polynomial Q(x) = c₀ + c₁·x + … + cₙ·xⁿ, the sum of its coefficients is  
       S = c₀ + c₁ + … + cₙ  
     but also Q(1) = c₀·1⁰ + c₁·1¹ + … + cₙ·1ⁿ = S.  
   - Therefore, the sum of coefficients of (a·x + b)^k is simply (a·1 + b)^k = (a + b)^k.  
   - Constraints (a,b ≤ 100, k ≤ 20) make direct exponentiation trivial and result fits in a 64-bit integer.

3. Full Solution Approach  
   1. Read the three integers a, b, k.  
   2. Compute S = (a + b)^k using integer exponentiation (O(log k) by binary exponentiation or O(k) by repeated multiplication).  
   3. Print S.

4. C++ Implementation with Detailed Comments  

```cpp
#include <bits/stdc++.h>
using namespace std;

// Compute x^e using binary (fast) exponentiation in O(log e)
unsigned long long int_pow(unsigned long long x, int e) {
    unsigned long long result = 1;
    while (e > 0) {
        if (e & 1) {
            result *= x;
        }
        x *= x;
        e >>= 1;
    }
    return result;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    unsigned long long a, b;
    int k;
    // Read input: coefficients a and b, exponent k
    cin >> a >> b >> k;

    // Key step: sum of coefficients = (a + b)^k
    unsigned long long base = a + b;
    unsigned long long answer = int_pow(base, k);

    // Output the result
    cout << answer << "\n";
    return 0;
}
```

5. Python Implementation with Detailed Comments  

```python
def main():
    # Read integers a, b, k from standard input
    a, b, k = map(int, input().split())

    # Sum of coefficients of (a*x + b)^k equals (a + b)^k
    result = pow(a + b, k)  # built-in pow handles large integers exactly

    # Print the result
    print(result)

if __name__ == "__main__":
    main()
```