Funksiya f(n)

Funksiya $f(n)$ aşağıdakı rekursiv əlaqə ilə təyin olunur:

f(n) = f(n-1) + f(n-2) + ... + f(2) + f(1),
f(1) = 1

$f(n)mod123456789$ dəyərini tapın.

Giriş verilənləri

Bir təbii ədəd $n(1\le n\le 10^9)$ verilmişdir.

Çıxış verilənləri

$f(n)mod123456789$ dəyərini çıxarın.

Nümunələr