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