#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cmath>
#include <cassert>
#include <sys/time.h>
using namespace std;
#define all(c) (c).begin(), (c).end()
#define iter(c) __typeof((c).begin())
#define cpresent(c, e) (find(all(c), (e)) != (c).end())
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define tr(c, i) for (iter(c) i = (c).begin(); i != (c).end(); ++i)
#define pb(e) push_back(e)
#define mp(a, b) make_pair(a, b)
#include <sys/time.h>
#include <unistd.h>
#include <stdarg.h>
struct __bench__ {
double start;
char msg[100];
__bench__(const char* format, ...)
__attribute__((format(printf, 2, 3)))
{
va_list args;
va_start(args, format);
vsnprintf(msg, sizeof(msg), format, args);
va_end(args);
start = sec();
}
~__bench__() {
fprintf(stderr, "%s: %.6f sec\n", msg, sec() - start);
}
double sec() {
struct timeval tv;
gettimeofday(&tv, NULL);
return tv.tv_sec + tv.tv_usec * 1e-6;
}
operator bool() { return false; }
};
#define benchmark(...) if(__bench__ __b__ = __bench__(__VA_ARGS__));else
typedef long long ll;
namespace pow_mod {
inline ll pow_mod(ll a, ll k, ll m) {
ll r = 1;
for (; k > 0; k >>= 1) {
if (k & 1) (r *= a) %= m;
(a *= a) %= m;
}
return r;
}
inline ll inverse(ll a, ll m) {
return pow_mod(a, m - 2, m);
}
}
namespace exgcd {
inline ll exgcd(ll a, ll b, ll &x, ll &y){
ll u[] = {a, 1, 0}, v[] = {b, 0, 1};
while(*v){
ll t = *u / *v;
rep(i, 3) swap(u[i] -= t * v[i], v[i]);
}
x = u[1]; y = u[2];
return u[0];
}
inline ll inverse(ll a, ll m){
ll p, q;
exgcd(a, m, p, q);
return (p%m+m)%m;
}
}
const ll MOD = 1000000009;
const int N = 1000000;
int main() {
int a;
scanf("%d", &a);
rep (i, 3) {
benchmark("pow_mod %d", i) {
ll t = a;
for (int k = 1; k <= N; ++k) {
t = pow_mod::inverse(t, MOD) * k % MOD;
}
printf("(%lld)\n", t);
}
}
rep (i, 3) {
benchmark("exgcd %d", i) {
ll t = a;
for (int k = 1; k <= N; ++k) {
t = exgcd::inverse(t, MOD) * k % MOD;
}
printf("(%lld)\n", t);
}
}
return 0;
}
I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8c3N0cmVhbT4KI2luY2x1ZGUgPHN0cmluZz4KI2luY2x1ZGUgPHZlY3Rvcj4KI2luY2x1ZGUgPHN0YWNrPgojaW5jbHVkZSA8cXVldWU+CiNpbmNsdWRlIDxzZXQ+CiNpbmNsdWRlIDxtYXA+CiNpbmNsdWRlIDxhbGdvcml0aG0+CiNpbmNsdWRlIDxjc3RkaW8+CiNpbmNsdWRlIDxjc3RkbGliPgojaW5jbHVkZSA8Y3N0cmluZz4KI2luY2x1ZGUgPGNjdHlwZT4KI2luY2x1ZGUgPGNtYXRoPgojaW5jbHVkZSA8Y2Fzc2VydD4KI2luY2x1ZGUgPHN5cy90aW1lLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CgojZGVmaW5lIGFsbChjKSAoYykuYmVnaW4oKSwgKGMpLmVuZCgpCiNkZWZpbmUgaXRlcihjKSBfX3R5cGVvZigoYykuYmVnaW4oKSkKI2RlZmluZSBjcHJlc2VudChjLCBlKSAoZmluZChhbGwoYyksIChlKSkgIT0gKGMpLmVuZCgpKQojZGVmaW5lIHJlcChpLCBuKSBmb3IgKGludCBpID0gMDsgaSA8IChpbnQpKG4pOyBpKyspCiNkZWZpbmUgdHIoYywgaSkgZm9yIChpdGVyKGMpIGkgPSAoYykuYmVnaW4oKTsgaSAhPSAoYykuZW5kKCk7ICsraSkKI2RlZmluZSBwYihlKSBwdXNoX2JhY2soZSkKI2RlZmluZSBtcChhLCBiKSBtYWtlX3BhaXIoYSwgYikKCiNpbmNsdWRlIDxzeXMvdGltZS5oPgojaW5jbHVkZSA8dW5pc3RkLmg+CiNpbmNsdWRlIDxzdGRhcmcuaD4KCnN0cnVjdCBfX2JlbmNoX18gewogIGRvdWJsZSBzdGFydDsKICBjaGFyIG1zZ1sxMDBdOwogIF9fYmVuY2hfXyhjb25zdCBjaGFyKiBmb3JtYXQsIC4uLikKICBfX2F0dHJpYnV0ZV9fKChmb3JtYXQocHJpbnRmLCAyLCAzKSkpCiAgewogICAgdmFfbGlzdCBhcmdzOwogICAgdmFfc3RhcnQoYXJncywgZm9ybWF0KTsKICAgIHZzbnByaW50Zihtc2csIHNpemVvZihtc2cpLCBmb3JtYXQsIGFyZ3MpOwogICAgdmFfZW5kKGFyZ3MpOwoKICAgIHN0YXJ0ID0gc2VjKCk7CiAgfQogIH5fX2JlbmNoX18oKSB7CiAgICBmcHJpbnRmKHN0ZGVyciwgIiVzOiAlLjZmIHNlY1xuIiwgbXNnLCBzZWMoKSAtIHN0YXJ0KTsKICB9CiAgZG91YmxlIHNlYygpIHsKICAgIHN0cnVjdCB0aW1ldmFsIHR2OwogICAgZ2V0dGltZW9mZGF5KCZ0diwgTlVMTCk7CiAgICByZXR1cm4gdHYudHZfc2VjICsgdHYudHZfdXNlYyAqIDFlLTY7CiAgfQogIG9wZXJhdG9yIGJvb2woKSB7IHJldHVybiBmYWxzZTsgfQp9OwoKI2RlZmluZSBiZW5jaG1hcmsoLi4uKSBpZihfX2JlbmNoX18gX19iX18gPSBfX2JlbmNoX18oX19WQV9BUkdTX18pKTtlbHNlCgoKCnR5cGVkZWYgbG9uZyBsb25nIGxsOwoKbmFtZXNwYWNlIHBvd19tb2QgewppbmxpbmUgbGwgcG93X21vZChsbCBhLCBsbCBrLCBsbCBtKSB7CiAgbGwgciA9IDE7CiAgZm9yICg7IGsgPiAwOyBrID4+PSAxKSB7CiAgICBpZiAoayAmIDEpIChyICo9IGEpICU9IG07CiAgICAoYSAqPSBhKSAlPSBtOwogIH0KICByZXR1cm4gcjsKfQoKaW5saW5lIGxsIGludmVyc2UobGwgYSwgbGwgbSkgewogIHJldHVybiBwb3dfbW9kKGEsIG0gLSAyLCBtKTsKfQp9CgpuYW1lc3BhY2UgZXhnY2QgewppbmxpbmUgbGwgZXhnY2QobGwgYSwgbGwgYiwgbGwgJngsIGxsICZ5KXsKICBsbCB1W10gPSB7YSwgMSwgMH0sIHZbXSA9IHtiLCAwLCAxfTsKICB3aGlsZSgqdil7CiAgICBsbCB0ID0gKnUgLyAqdjsKICAgIHJlcChpLCAzKSBzd2FwKHVbaV0gLT0gdCAqIHZbaV0sIHZbaV0pOwogIH0KICB4ID0gdVsxXTsgeSA9IHVbMl07CiAgcmV0dXJuIHVbMF07Cn0KaW5saW5lIGxsIGludmVyc2UobGwgYSwgbGwgbSl7CiAgbGwgcCwgcTsKICBleGdjZChhLCBtLCBwLCBxKTsKICByZXR1cm4gKHAlbSttKSVtOwp9Cn0KCgoKY29uc3QgbGwgTU9EID0gMTAwMDAwMDAwOTsKY29uc3QgaW50IE4gPSAxMDAwMDAwOwoKaW50IG1haW4oKSB7CiAgaW50IGE7CiAgc2NhbmYoIiVkIiwgJmEpOwoKICByZXAgKGksIDMpIHsKICAgIGJlbmNobWFyaygicG93X21vZCAlZCIsIGkpIHsKICAgICAgbGwgdCA9IGE7CiAgICAgIGZvciAoaW50IGsgPSAxOyBrIDw9IE47ICsraykgewogICAgICAgIHQgPSBwb3dfbW9kOjppbnZlcnNlKHQsIE1PRCkgKiBrICUgTU9EOwogICAgICB9CiAgICAgIHByaW50ZigiKCVsbGQpXG4iLCB0KTsKICAgIH0KICB9CiAgcmVwIChpLCAzKSB7CiAgICBiZW5jaG1hcmsoImV4Z2NkICVkIiwgaSkgewogICAgICBsbCB0ID0gYTsKICAgICAgZm9yIChpbnQgayA9IDE7IGsgPD0gTjsgKytrKSB7CiAgICAgICAgdCA9IGV4Z2NkOjppbnZlcnNlKHQsIE1PRCkgKiBrICUgTU9EOwogICAgICB9CiAgICAgIHByaW50ZigiKCVsbGQpXG4iLCB0KTsKICAgIH0KICB9CgogIHJldHVybiAwOwp9Cg==