Description

设 \(A=(\frac{3+\sqrt{5}}{2})^n\), \(B=1004535809\).
计算: \(\left \lfloor A \right \rfloor\ mod\ B\)

(注：第一行中A为 ((3+sqrt(5))/2)^n )

Format

Input

包含多组输入数据，每行一个自然数\(n(n \leq 10^{18})\)
输入数据组数\(\leq 10^5\)

Output

对于每组输入数据，输出一行一个整数，表示题目中需要计算的数。

Sample 1

Input

0
5
1000000000000000000

Output

1
122
409829663

Limitation

1s, 1024KiB for each test case.

Hint

本题时限比较紧张，请注意你的程序的执行效率。

Free Pascal Code

var a,b:longint;
begin
    readln(a,b);
    writeln(a+b);
end.

C Code

#include <stdio.h>
int main(void)
{
    int a, b;
    scanf("%d%d", &a, &b);
    printf("%d\n", a + b);
    return 0;
}

C++ Code

#include <iostream>
using namespace std;
int main()
{
    int a, b;
    cin >> a >> b;
    cout << a + b << endl;
    return 0;
}

Python Code

a, b = [int(i) for i in raw_input().split()]
print(a + b)

Java Code

import java.io.*;
import java.util.Scanner;

public class Main {

    /**
     * @param args
     * @throws IOException 
     */
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int b = sc.nextInt();
        System.out.println(a + b);
    }
}

Source

Vijos Original