"use strict";
    
const permutateWithRepetitions = (
  permutationOptions,
  permutationLength
) => {
  if (permutationLength === 1) {
    return permutationOptions.map(permutationOption => [permutationOption]);
  }

  // Init permutations array.
  const permutations = [];

  // Get smaller permutations.
  const smallerPermutations = permutateWithRepetitions(
    permutationOptions,
    permutationLength - 1,
  );

  // Go through all options and join it to the smaller permutations.
  permutationOptions.forEach((currentOption) => {
    smallerPermutations.forEach((smallerPermutation) => {
      permutations.push([currentOption].concat(smallerPermutation));
    });
  });

  return permutations;
}

// 組み合わせ（nCr）列挙ではなく計算のみ
const permutation = (n, r) => {
    let res = 1;
    
    for(let i=0; i<r; i++) {
        res *= (n - i);
    }
    
    return res;
}
 
const combination = (n, r) => {
    return permutation(n, r) / permutation(r, r);
}

const main = arg => {
    arg = arg.trim().split("\n");
    const N = parseInt(arg[0].split(" ")[0]);
    const MOD = 1e9;
    
    // const hage = permutateWithRepetitions([0,1,2,3,4,5,6,7,8,9], 3);
    // let cnt = 0;
    
    // for(let i in hage) {
    //     if(hage[i].filter(n=>n===0).length && hage[i].filter(n=>n===9).length) {
    //         cnt++;
    //         //console.log(hage[i]);
    //     }
    // }
    
    // console.log(cnt);
    //console.log(permutation(N, 2));
    if(N === 1) {
        console.log(0);
        return;
    }
    
    if(N === 2) {
        console.log(2);
        return;
    }
    
    const p = permutation(N, 2);
    
    let temp = 9;//(Math.pow(9, (N - 2))) % MOD;
    
    for(let i=1; i<N-2; i++) {
        temp = (temp * 9) % MOD;
    }
    
    console.log((temp * p) % MOD)
    
}
main(require('fs').readFileSync('/dev/stdin', 'utf8'));