#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <map>
#include <cassert>
#define int long long

using namespace std ;

const int N = 2e7 + 5 , M = 2e5 + 5 , mod = 1e9 + 7 ; 

namespace BINOM {
    int inv[N] , ifac[N] , fac[N] ;
    int binom_init(int n = N) {
        inv[1] = fac[0] = ifac[0] = 1 ; 
        for (int i = 2 ; i < n ; ++ i) inv[i] = 1ll * (mod - mod / i) * inv[mod % i] % mod ; 
        for (int i = 1 ; i < n ; ++ i) {
            fac[i] = 1ll * fac[i - 1] * i % mod ; 
            ifac[i] = 1ll * ifac[i - 1] * inv[i] % mod ; 
        }
        return 0 ; 
    }
    int get_binom = binom_init() ;
    int C(int n , int m) {
        if (n < m || m < 0) return 0 ;
        return 1ll * fac[n] * ifac[m] % mod * ifac[n - m] % mod ; 
    }
} 
using namespace BINOM ; 

int qmi(int a , int b = mod - 2) {
    int res = 1;
    while (b) {
        if (b & 1) res = (long long)res * a % mod;
        a = (long long)a * a % mod , b >>= 1;
    }
    return res;
}
int n ; 
int f[21][M] , pw[20] ;

void add(int &x , int y) { if ((x += y) >= mod) x -= mod ; }

// int cnt ; 
int dfs(int i , int j) {
    // ++ cnt ;
    // assert(j >= 0) ;
    if (f[i][j] != -1) return f[i][j] ;
    if (j == 0) return 0 ;

    int res = 1 ; 
    int x = min(n - pw[i] - j , j) , y = min(2 * pw[i] , n - pw[i]) ; 

    int tot = qmi(C(n - pw[i] , y)) ; 
    for (int t = 0 ; t <= min(j + x , y) ; ++ t) {
        int fs = C(j + x , t) * C(n - pw[i] - j - x , y - t) % mod ; 
        fs = fs * tot % mod ;
        if (fs)
            add(res , fs * dfs(i + 1 , j + x - t) % mod) ; 
    }

    return f[i][j] = res ; 
}

signed main()
{
    memset(f , -1 , sizeof f) ; 
    pw[0] = 1 ; 
    for (int i = 1 ; i < 20 ; ++ i) pw[i] = pw[i - 1] * 3 ; 

    cin >> n ; 
    cout << dfs(0 , 1) << '\n' ; 
    // cout << cnt << '\n' ; 
    return 0 ; 
}