A uma dada altura, a formiga viaja de um vértice para outro através de uma das várias arestas do tetraedro, e a tarefa apresentada não envolve muitos cálculos.
Simplesmente, calculem o número de maneiras em que a formiga pode ir do vértice inicial D, de volta a ele próprio em apenas N passos.
Novamente, o resultado pode ser enorme, logo, devolvam-no reportado mod

Exemplos:
Claramente, para N = 1 não há caminhos possíveis.
Para N = 2 a resposta é 3, e os caminhos possíveis são: D-B-D; D-A-D; D-C-D
Sabe-se ainda que, para N= 4, a resposta é 21!!

Have fun!!
Bruno
source: CodeForces