// Arup Guha
// 10/12/2022
// Computes g(n) mod 1000000007 for n upto 1000 from Fall 2022 COT 3100 Homework #5 Question #4

#include <stdio.h>
#include <stdlib.h>

#define MAX 1000

#define MOD 1000000007ll

int main(void) {

    // Allocate memory and seed starting values.
    long long* vals = calloc(MAX+1,sizeof(long long));
    vals[0] = 0;
    vals[1] = 2;
    vals[2] = 2;
    vals[3] = 3;

    // Just calculate each successive value based on recursive formula.
    for (int i=4; i<=MAX; i++)
        vals[i] = (3*vals[i-1]+vals[i-2] + vals[i-3])%MOD;

    // Output results.
    for (int i=1; i<=MAX; i++)
        printf("%d %lld\n", i, vals[i]);

    // Clean up.
    free(vals);

    return 0;
}