10844.c

#include <stdio.h>

long long a[101][10];
long long s[101];

int main() {

	int n;

	scanf("%d", &n);

	a[1][0] = 0;
	for (int i = 1; i < 10; i++) {
		a[1][i] = 1;
		s[1] ++;
	}

	for (int i = 2; i <= n; i++) {
		if (i == 2)
			a[i][1] = 2;
		else
			a[i][1] = (a[i - 2][1] + a[i - 1][2]) % 1000000000;
		a[i][2] = (a[i - 1][1] + a[i - 1][3]) % 1000000000;
		a[i][3] = (a[i - 1][2] + a[i - 1][4]) % 1000000000;
		a[i][4] = (a[i - 1][3] + a[i - 1][5]) % 1000000000;
		a[i][5] = (a[i - 1][4] + a[i - 1][6]) % 1000000000;
		a[i][6] = (a[i - 1][5] + a[i - 1][7]) % 1000000000;
		a[i][7] = (a[i - 1][6] + a[i - 1][8]) % 1000000000;
		a[i][8] = (a[i - 1][7] + a[i - 1][9]) % 1000000000;
		a[i][9] = a[i - 1][8] % 1000000000;
		for (int j = 1; j <= 9; j++)
			s[i] += a[i][j] % 1000000000;
	}

	printf("%lld", s[n] % 1000000000);

	return 0;
}