SPOJ in Gyumri

   ՀԱՊՀ Գյումրու մասնաճյուղի «Սպորտային ծրագրավորման» դպրոցի սաները հորինել են մի հաջորդականություն, որը սահմանվում է հետևյալ կերպ.

որտեղ x-ը և y-ը տրված ամբողջ թվեր են:

   Ձեր խնդիրն է գրել ծրագիր, որի արդյունքում տրված n թվի համար կստանաք հաջորդականության n–րդ անդամը 1000000007-ի բաժանելուց ստացված մնացորդը:

Մուտքային տվյալներ.

    Մուտքի առաջին տողում տրված են x և y ամբողջ թվերը, որոնք բացարձակ արժեքով չեն գերազանցում 10⁹-ը: Մուտքի երկրորդ տողում տրված է n բնական թիվը (1 ≤ n ≤ 2·10⁹):

Ելքային տվյալներ.

   Ելքում պետք է արտածել խնդրի պատասխանը:

Օրինակներ.

N


stdin


stdout




1


2 3

3



1




2


0 -1

2



1000000006