s[i] = (a, b, c, d)
=>
s[i + 1].a = s[i].b + s[i].c + s[i].d
s[i + 1].b = s[i].a + s[i].c + s[i].d
s[i + 1].c = s[i].a + s[i].b + s[i].d
s[i + 1].d = s[i].a + s[i].b + s[i].c
=>
s[i + 1]  = s[i] * ( 0 1 1 1 ) = s[i] * M
                   ( 1 0 1 1 )
                   ( 1 1 0 1 )
                   ( 1 1 1 0 )
=>
s[i + k] = s[i] * (M pow k)
=>
s[0].d = 1;
s[n] = s[0] * (M pow n)
ans = s[n].d

The fastest matrix multiplication algorithm is Strassen_algorithm then you have to apply Binary Exponentiation .

Tetrahedron can be represented as a graph with 4 vertices and problem is to count number of ways with fixed length K. There is an explanation of the solution with matrix exponentiation: here