#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; //-------------------------- int main() { int n; cin >> n; if (n == 0) { cout << 1 << endl; return 0; } long double d = 1 + sqrt(3); ll m; int i = 1; while (i < n) { d = d * d; m = d; d = d - m; d = d + m % 1000; i = i * 2; } if (i != n) { i = i / 2; while (i < n) { d = d * (1 + sqrt(3)); m = d; d = d - m; d = d + m % 1000; i++; } } cout << (int)d % 1000 << endl; return 0; }