Yo`nalishlar
Hozirda online

Statistika

Masalalar soni: 909

Foydalanuvchilar soni: 8819

Jo'natishlar soni: 714318

Muhokama yozuvlari: 4540

Yangiliklar soni: 97

Yangiliklar izohlari: 1174


So'ngi izohlar

732. Function
Vaqt limiti: 1 sekund
Xotira limiti: 64 MB

Calculate the function: 

Описание: Описание: prb1868-e   




Input

One positive integer n (1 ≤ n ≤ 1012).

   Output                                     

The value of f(n) modulo 1000000009.

 Samples                                 

Input

Output

1

7

10

 

Tayyorladi: Azat Yusupov
Text from: e-olimp.com
Mening urinishlarim(0) Muhokama (0) Jo'natish Eng yaxshi yechimlar Barcha muvaffaqiyatli urinishlar(18) Barcha urinishlar(161)