#OK to post homework
#TianHao Zhang,04/20/19
#################################Help#######################################
Help:=proc():print(`F(n,K) Tc(n,K)`) end:
#################################Part1######################################
F:=proc(n,K) local B,C,i:
B:=Matrix([[1,1],[1,0]]):
C:=Matrix([[1],[0]]):
convert((B^n.C mod K),list)[1]:
end:

#>F(10^6, 2003)
# 1998 
#(Very fast!)
#################################Part2######################################
#Tc(n,K): that finds the n-th Tribonacci number mod K.
Tc:=proc(n,K) local i,B,C,b:
B:=Matrix([[1,1,1],[1,0,0],[0,1,0]]):
C:=Matrix([[1],[0],[0]]):
b:=FastC(B,n,K):
convert((b.C mod K),list)[1]:
end:

#FastC(B,n,K): a faster way to compute the matrix with exponential.
FastC:=proc(B,n,K):
if n < 10 then
  return(B^n mod K):
else
  return((FastC(B,n/10,K) mod K)^10):
fi:
end:

#Tc(10^100, 2003);
#                              1995
#(Very fast!)