Along Seabreak Path, there are $$$N = 3^K$$$ rows of flowers, with each row containing exactly $$$K$$$ flowers. In the $$$i$$$-th row ($$$0 \leq i \leq N - 1$$$), the color of the flowers is denoted by the ternary representation of $$$i$$$, with $$$0$$$ representing red, $$$1$$$ representing green, and $$$2$$$ representing blue.

E.g., if $$$K = 4$$$ and $$$i = 38 = 1102_{3}$$$. Then, the flowers in the $$$38$$$th ($$$0$$$-indexed) row are green, green, red, and blue, in that order.

Shaymin likes each row of flowers a different amount, so they assign a beauty value $$$B_{i}$$$ to each row, where $$$B$$$ is a permutation from $$$0$$$ to $$$N - 1$$$.

Two rows $$$i$$$ and $$$j$$$ are considered independent if they do not have any identical flowers in the same column.

E.g., row $$$i = 3 = 0010_{3}$$$ and row $$$j = 38 = 1102_{3}$$$ are independent, while row $$$i = 3 = 0010_{3}$$$ and row $$$j = 22 = 0211_{3}$$$ are not independent because the first flowers are both red, and the third flowers are both green.

Two rows $$$i$$$ and $$$j$$$ are considered an independent inversion if:

• $$$i \lt j$$$
• $$$B_{i} \gt B_{j}$$$
• Rows $$$i$$$ and $$$j$$$ are independent.

Help Shaymin count the number of independent inversions in Seabreak Path!