JADDOU3 - Jaddouic Sequence

 

Jadou has created another boring sequence, he wrote the 1st 5 numbers on a stone, 300 years later Hasan Jadou Jr. found the stone and wanted to find the nth element of the sequence.
The numbers written on the stone were...
1, 10 , 36 , 136 ,528
Help Jadou find the rest of the sequence.
print the nth element of the Jadou sequence
mod 123456789

 

Jadou has created another boring sequence, he wrote the 1st 5 numbers on a stone, 300 years later Hasan Jadou Jr. found the stone and wanted to find the nth element of the sequence.

The numbers written on the stone were...

3, 10 , 36 , 136 ,528.

Jaddou junior descovered that the elements of the sequence are always even except the 1st one.

Help Jadou find the rest of the sequence.

print the nth element of the Jaddou sequence

mod 123456789

 

 

Input

One integer n.(0<n<10^18)

Output

The nth element of the Jaddou sequence mod 123456789.

Example

Input:
5
Output:
528 

Added by:Aleksandar Abas
Date:2013-03-27
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Own Problem

hide comments
2014-02-13 14:02:14 Anubhav Balodhi
Is the ans for 10^18 = 32810158 ?!

Last edit: 2014-02-13 14:24:28
2013-11-05 20:08:03 ROHIT RAWAT
getting wa, although code is working for above cases. please tell me where it is going wrong
RE: Check your code you aren't outputting anything...

Last edit: 2013-11-11 21:30:45
2013-08-10 18:59:19 Pratyush Kumar
Give more test cases.
Re: There are enough test cases to solve the riddle...

Last edit: 2013-10-31 17:35:57
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.