#!/usr/bin/env python3
P = 998244353

def computeT(d, gy):
    Sv = [0] * (d + 1)
    for j in range(d):
        c = (Sv[j] - Sv[gy[j]] + (j - gy[j]) + 1) % P
        Sv[j + 1] = (Sv[j] + c) % P
    return (Sv[d] + d + 1) % P

d = 27
target1 = 150994941
target2 = 150994939

# Search ALL two-change combinations (not just first find)
print("All two-change solutions for d=27:")
for j1 in range(d):
    for g1 in range(1, j1+1):
        for j2 in range(j1+1, d):
            for g2 in range(1, j2+1):
                gy = [0]*d
                gy[j1] = g1
                gy[j2] = g2
                T = computeT(d, gy)
                if T == target1:
                    print(f"TARGET1: gy[{j1}]={g1}, gy[{j2}]={g2}")
                if T == target2:
                    print(f"TARGET2: gy[{j1}]={g1}, gy[{j2}]={g2}")

# Now try with SMALLER d values!
print("\nSearching smaller d values with multi-change:")
for d in range(20, 27):
    print(f"\n=== d={d} (n={d+1}) ===")
    # For smaller d, we need more changes.
    # Let's try exhaustive search with up to 4 changes using hill climbing
    import random
    random.seed(42 + d)

    best_gy = None
    for trial in range(100000):
        gy = [0] * d
        # Random: set 1-6 positions to non-zero
        num_changes = random.randint(1, min(6, d))
        positions = random.sample(range(1, d), min(num_changes, d-1))
        for j in positions:
            gy[j] = random.randint(0, j)

        T = computeT(d, gy)
        if T == target1:
            print(f"FOUND TARGET1 d={d}: gy = {gy}")
            best_gy = gy[:]
            break
        if T == target2:
            print(f"FOUND TARGET2 d={d}: gy = {gy}")
            best_gy = gy[:]
            break

    if best_gy is None:
        # Hill climbing
        for restart in range(200):
            gy = [0] * d
            for j in range(1, d):
                gy[j] = random.randint(0, j)
            T = computeT(d, gy)

            for iteration in range(50000):
                j = random.randint(1, d-1)
                old_g = gy[j]
                gy[j] = random.randint(0, j)
                nT = computeT(d, gy)

                if nT == target1 or nT == target2:
                    print(f"FOUND d={d}: T={nT}, gy = {gy}")
                    best_gy = gy[:]
                    break

                nd = min((nT - target1) % P, (target1 - nT) % P, (nT - target2) % P, (target2 - nT) % P)
                od = min((T - target1) % P, (target1 - T) % P, (T - target2) % P, (target2 - T) % P)

                if nd <= od:
                    T = nT
                else:
                    gy[j] = old_g

            if best_gy: break