Shield Sequence

The letters from home were finally readable. Chorba frik recipes from mothers, photos of zlabia and kalb el louz fresh from the kitchen, voice notes from cousins wishing them Ramadan Mabrouk. The crew pinned printed messages on the cabin walls and someone taped a photo of a mawa'id ar-rahma table to the galley door. The last days of Ramadan had arrived, and through the viewport, the blue curve of Earth was growing larger every day.

But the homecoming was not guaranteed yet. The rocket's radiation shield generator, the only thing standing between the crew and lethal reentry radiation, needed a calibration cipher to arm. The generator used a pseudo-random number system driven by a 64-bit internal state that evolved according to a linear congruential formula. The crew pulled the generator's parameters from a diagnostic memory dump: the initial seed, the multiplier, and the increment. The calibration protocol required two things: a verification checksum computed from the generator's first N outputs, and a diagnostic state reading at step T, where T could be in the quadrillions. Without both values, the shields would not arm, and reentry would be fatal.

Adel stared at the numbers on the screen. "We compute these or we don't go home for Eid."

Input Format

A single line: S0 MULT INC N T P

• S0 — the initial seed (64-bit unsigned integer).
• MULT — the multiplier (odd 64-bit unsigned integer).
• INC — the increment (odd 64-bit unsigned integer).
• N — the short-range verification step count (5,000 to 15,000).
• T — the long-range calibration index (up to 10^18).
• P — the diagnostic modulus (prime, approximately 10^9).

Generator Structure

Stage 1 — State Update (Linear Congruential Generator):

At each step k (starting from k=1), the state advances according to the standard LCG recurrence:

S(k) = (S(k-1) * MULT + INC) mod 2^64

• S(0) = S0 is the initial seed given in the input.
• All arithmetic is unsigned 64-bit (values wrap modulo 2^64).
• The LCG period is maximal (2^64) since both MULT and INC are odd.

Stage 2 — Output Transformation (PCG-XSH-RR):

The standard PCG output permutation is applied to the new state S(k) to produce a 32-bit output:

xorshifted = ((state >> 18) ^ state) >> 27 rot = state >> 59 output = (xorshifted >> rot) | (xorshifted << ((-rot) & 31))

• >> is unsigned (logical) right shift. << is left shift.
• ^ is bitwise XOR, & is bitwise AND.
• xorshifted is a 32-bit value.
• rot is a 5-bit value (0 to 31).
• output is a 32-bit unsigned integer.

For the calibration checksum, the top 16 bits are extracted from each output: value = output >> 16 (yielding a value from 0 to 65535).

Step 1: Advance to S(1), then output_1 = PCG(S(1)) Step 2: Advance to S(2), then output_2 = PCG(S(2)) Step 3: Advance to S(3), then output_3 = PCG(S(3))

Run the generator for exactly N steps. At each step, apply the PCG-XSH-RR output transformation and extract the top 16 bits. Compute the checksum: the sum of all N extracted values.

Output: The sum as a single integer.

Example Input

7392142408732208350 8796093023223 2199023257957 14334 300323046467736761 1000027013

Example Walkthrough

With S0 = 7392142408732208350, MULT = 8796093023223, INC = 2199023257957:

The first three outputs for verification:

With N = 14334: Answer: 474629084.

What is the checksum over the first N steps?