工作之余，zxa 喜欢玩汉诺塔，他曾经花费大量时间手玩过 $61$ 层的汉诺塔，这一壮举震撼了整个山东。
大家都知道汉诺塔问题：给定一个由 $n$ 个圆盘组成的塔，这些圆盘按照大小递减的方式套在三根桩柱中的一根上，我们的目的是要将整个塔移动到另一根桩柱上，每次只能移动一个圆盘，且较大的圆盘在移动过程中不能放置在较小的圆盘上面。
我们都知道最少需要 $2^n-1$ 步来完成这个游戏，但是zxa觉得这样不够刺激，他将三个桩柱分别编号为 1，2，3，初始塔在 1 号桩柱上，我们要将塔移动到 3 号桩柱上，他规定了所有三个桩柱之间能否直接移动的关系，即对于第 $i(1\le i\le3)$ 号桩柱上的一个圆盘，能否直接移动到第 $j(1\le j\le3,i\neq j)$ 号桩柱上。这样之后，他弄不明白是否还能移动，以及需要的最少步数了，你能帮帮他吗？如果不能移动，输出 -1，否则输出最少需要的步数对 $10^9+7$ 取模之后的值。
第一行一个数 $T$ 表示数组组数。
对于每组数据：第一行一个数字 $n$ ，表示圆盘数量。接下来 3 行，每行 3 个数，对于第 $i$ 行的第 $j$ 个数，表示第 $i$ 个桩柱上的圆盘能否直接移动到 $j$ 号桩柱上，若 $i=j$ ，必定为 1。
其中，$1\le T\le 500$，$1\le n\le 10^9$
对于每组数据，输出一行，若不能移动，输出 -1，否则输出最少需要的步数对 $10^9+7$ 取模之后的值。
1
61
1 1 1
1 1 1
1 1 172793000