Jzzhu and Sequences

Back to problems

Codeforces

Medium

Arrays

Math

Number Theory

Google

Jzzhu and Sequences

Given the first two values of a sequence defined by a Fibonacci-like recurrence, answer the n-th term modulo $10^9+7$ .

Acceptance 0%

Start Practice

Problem Statement

You are given two integers $x$ and $y$ that define a sequence $a$ as follows:

$a_1 = x$
$a_2 = y$
For every $i \ge 3$ , $a_i = a_{i-1} - a_{i-2}$

For a given index $n$ , compute the value of $a_n$ modulo $10^9 + 7$ .

Because the values can become negative, the answer should always be reported in the standard non-negative modulo form.

This is a direct sequence-evaluation problem with a repeating pattern in the recurrence.

Input Format

A single line containing three integers $x$ , $y$ , and $n$ .

Output Format

Print one integer: $a_n \bmod (10^9+7)$ .

Constraints

$1 \le n$
$x$ and $y$ fit in 64-bit signed integers
Output the result in the range $[0, 10^9+6]$

Examples

Sample cases returned by the problem API.

Example 1

Input

1 2 1

Output

Explanation

The first term is $a_1 = 1$ .

Example 2

Input

1 2 4

Output

Explanation

The sequence is $1, 2, 1, -1, \dots$ , so $a_4 = -1 \equiv 10^9+6 \pmod{10^9+7}$ . For illustration, the sample output format here shows the direct value modulo normalization would be used in practice.

Premium problem context

Unlock deeper context for this problem

Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.

Guided hints

Editorial and discussion links

Concept map and variants

Track your progress