10844

#include <stdio.h>

int divisor = 1000000000;

int main()
{
    int n;
    scanf("%d", &n);

    unsigned long long dp[101][10] = {};

    dp[1][0] = 0;
    for (int i = 1; i < 10; i++)
        dp[1][i] = 1;

    
    for (int i = 2; i <= n; i++)
    {
        for (int j = 0; j <= 9; j++)
        {
            dp[i][j] = (((j-1>=0)?dp[i - 1][j - 1]:0) + ((j+1<=9)?dp[i - 1][j + 1]:0))%divisor;
        }
    }
    
    unsigned long long sum = 0;
    for (int i = 0; i <= 9; i++)
    {
        sum += dp[n][i];
    }

    sum = sum%divisor;

    printf("%d\n", sum);

    return 0;
}

100000000int divisor = 1000000000;

unsigned long long... 제발