// yukicoder: No.492 IOI数列 // 2019.4.17 bal4u // // 101数の第n項目: // a_1 = 1, a_2 = 100+1, a_3 = 100^2+100+1, a_n = (100^n-1)/99 // // mod m (m=10^9+7)についてのメモ // mは素数。99^(-1)つまり99の逆元=99^(m-2)=646464651 なので // (100^n-1)/99 mod m → (100^(n%(m-1))+m-1)*646464651 mod m #include #define MOD 1000000007 // 10^9+7 int bigPow(int x, int p, int mod) { int r = 1; while (p) { if (p & 1) r = (long long)r * x % mod; x = (long long)x * x % mod; p >>= 1; } return (r % mod); } int calc_109_7(long long n) { int p = (int)(n % (MOD-1)); long long a = bigPow(100, p, MOD); a = (a + MOD-1) * 646464651LL; return a % MOD; } int main() { int k; long long N; scanf("%lld", &N); printf("%d\n", calc_109_7(N)); putchar('1'); k = (int)(N % 11)-1; while (k--) putchar('0'), putchar('1'); putchar('\n'); return 0; }