lcb-0082

1.000

4/4 tests· algorithms

Proposed solution

I'll solve this step by step.

## Problem Understanding

We need to calculate the sum of a geometric series:
X = N^0 + N^1 + N^2 + ... + N^M

This is a geometric series with:
- First term a = 1
- Common ratio r = N
- Number of terms = M + 1

The formula for geometric series sum is: X = (r^(M+1) - 1) / (r - 1)) when r ≠ 1

In our case: X = (N^(M+1) - 1) / (N - 1))

However, since we're dealing with potentially large numbers, I should also consider:
1. Direct computation of each term
2. Using the geometric series formula
3. Checking if result exceeds 10^9

## Approach

Let me think about the constraints:
- N can be up to 10^9
- M can be up to 100
- So N^M could be very large

I'll use the geometric series formula: X = (N^(M+1) - 1) / (N - 1)

But I need to be careful with integer overflow and also check if the result exceeds 10^9.

Actually, let me reconsider. Since M ≤ 100, even if N = 10^9, we have N^M which could be extremely large. But we can use the formula approach.

Wait, let me trace through Sample 1:
N=7, M=3
X = 7^0 + 7^1 + 7^2 + 7^3 = 1 + 7 + 49 + 343 = 400

Using geometric formula: X = (7^4 - 1) / (7 - 1) = (2401 - 1) / 6 = 2400 / 6 = 400 ✓

## Implementation Plan

1. Read N and M
2. Calculate the geometric series sum using formula: (N^(M+1) - 1) / (N - 1)
3. Check if result > 10^9, if so print "inf"
4. Otherwise print the result

But I need to be careful with integer overflow in Python. Actually, Python handles big integers well, but let me check if there's a simpler approach.

Let me also consider that we might want to compute it iteratively to avoid potential issues:

## Better Approach

I'll compute each term and sum them up:
- Start with sum = 1 (N^0)
- For i from 1 to M: multiply by N and add to sum
- Check if sum > 10^9 at each step

Actually, let me just use the mathematical formula since it's cleaner.

## Code Implementation

```python
# Read input
N, M = map(int, input().split())

# Calculate geometric series sum using formula: (N^(M+1) - 1) / (N - 1)
# This is sum of N^0 + N^1 + ... + N^M
if N == 1:
    # Special case: if N=1, then all terms are 1, so sum = M+1
    X = M + 1
else:
    # Use geometric series formula
    X = (N**(M+1) - 1) // (N - 1)

# Check if result exceeds 10^9
if X > 10**9:
    print("inf")
else:
    print(X)
```

Let me verify with the examples:

Sample 1: N=7, M=3
X = (7^4 - 1) // (7-1) = (2401 - 1) // 6 = 2400 // 6 = 400 ✓

Sample 2: N=1000000, M=2  
X = (1000000^3 - 1) // 999999 = (1000000000000000000 - 1) // 999999 = 1000000000000000000 // 999999 = 1000001000001 > 10^9 → "inf" ✓

This looks correct. Let me double-check the edge case when N=1:

If N=1, then all terms are 1, so sum = M+1.

```python
# Read input
N, M = map(int, input().split())

# Calculate geometric series sum using formula: (N^(M+1) - 1) / (N - 1)
# This is sum of N^0 + N^1 + ... + N^M
if N == 1:
    # Special case: if N=1, then all terms are 1, so sum = M+1
    X = M + 1
else:
    # Use geometric series formula
    X = (N**(M+1) - 1) // (N - 1)

# Check if result exceeds 10^9
if X > 10**9:
    print("inf")
else:
    print(X)
```

Test output (stdout)

....                                                                     [100%]
4 passed in 0.06s

System prompt

You are an expert programmer. Solve the task exactly as specified. Output your solution as fenced code blocks using the required file name(s) and the exact function/type signatures requested. Prefer correctness; do not include prose outside code unless asked.