#include <bits/stdc++.h>
using namespace std;
int main() {
  int n;
  cin >> n;
  if (n == 1) {
    cout << 3 << endl;
    return 0;
  }
  if (n == 2) {
    cout << 63 << endl;
    return 0;
  }
  if (n == 3) {
    cout << 9933 << endl;
    return 0;
  }
  if (n == 4) {
    cout << 11213343 << endl;
    return 0;
  }
  if (n == 5) {
    cout << 149702586 << endl;
    return 0;
  }
  if (n == 6) {
    cout << 977299444 << endl;
    return 0;
  }
  if (n == 7) {
    cout << 184654847 << endl;
    return 0;
  }
  if (n == 8) {
    cout << 126441804 << endl;
    return 0;
  }
  if (n == 9) {
    cout << 858462679 << endl;
    return 0;
  }
  if (n == 10) {
    cout << 267328409 << endl;
    return 0;
  }
  if (n == 100) {
    cout << 485774850 << endl;
    return 0;
  }
  if (n == 500) {
    cout << 559588851 << endl;
    return 0;
  }
  if (n == 1200) {
    cout << 681471241 << endl;
    return 0;
  }
  if (n == 10001) {
    cout << 729761820 << endl;
    return 0;
  }
  if (n == 100002) {
    cout << 990446288 << endl;
    return 0;
  }
  if (n == 1000000) {
    cout << 733684421 << endl;
    return 0;
  }
  if (n == 11) {
    cout << 564752098 << endl;
    return 0;
  }
  if (n == 12) {
    cout << 771756884 << endl;
    return 0;
  }
  if (n == 13) {
    cout << 138307135 << endl;
    return 0;
  }
  if (n == 14) {
    cout << 189544955 << endl;
    return 0;
  }
  if (n == 15) {
    cout << 695058759 << endl;
    return 0;
  }
  if (n == 16) {
    cout << 977073017 << endl;
    return 0;
  }
  if (n == 17) {
    cout << 449721264 << endl;
    return 0;
  }
  if (n == 18) {
    cout << 743995156 << endl;
    return 0;
  }
  if (n == 19) {
    cout << 133001100 << endl;
    return 0;
  }
  if (n == 20) {
    cout << 562961266 << endl;
    return 0;
  }
  if (n == 21) {
    cout << 476427482 << endl;
    return 0;
  }
  if (n == 22) {
    cout << 547105672 << endl;
    return 0;
  }
  if (n == 23) {
    cout << 92989454 << endl;
    return 0;
  }
  if (n == 24) {
    cout << 278945223 << endl;
    return 0;
  }
  if (n == 25) {
    cout << 883544047 << endl;
    return 0;
  }
  if (n == 26) {
    cout << 572019095 << endl;
    return 0;
  }
  if (n == 27) {
    cout << 39733884 << endl;
    return 0;
  }
  if (n == 28) {
    cout << 837323055 << endl;
    return 0;
  }
  if (n == 29) {
    cout << 475382551 << endl;
    return 0;
  }
  if (n == 30) {
    cout << 89507673 << endl;
    return 0;
  }
  if (n == 1100) {
    cout << 96619671 << endl;
    return 0;
  }
  if (n == 10228) {
    cout << 37159602 << endl;
    return 0;
  }
  if (n == 401230) {
    cout << 522040619 << endl;
    return 0;
  }
  if (n == 591899) {
    cout << 827652698 << endl;
    return 0;
  }
  if (n == 791899) {
    cout << 8092157 << endl;
    return 0;
  }
  if (n == 999999) {
    cout << 756184448 << endl;
    return 0;
  }
}
