P9416 [POI 2021/2022 R1] Domino

Translated from [XXIX Olimpiada Informatyczna – Stage I](https://sio2.mimuw.edu.pl/c/oi29-1/dashboard/) [Domino](https://sio2.mimuw.edu.pl/c/oi29-1/p/dom/)。

> There is a $2$-row, $n$-column rectangle, where some cells are blocked. You need to use $1\times 2$ or $2\times 1$ dominoes to cover all unblocked cells, and no cell may be covered twice. Let the number of ways be $m$. Given $m$, find the smallest $n$ such that there exists a way to choose the blocked cells so that the number of tilings is exactly $m$. If there is no solution, output `NIE`.

One line with a positive integer $m$。

If there is a solution, output your answer $n$。 If there is no solution, output `NIE`。

For all testdata, $1\leq m\leq 10^{18}$。 ## Constraints | Subtask ID | Additional Constraints | Score | | :----------: | :----------: | :----------: | | 1 | Answer $\leq 12$ | 20 | | 2 | $m\leq 2000000$ | 30 | | 3 | | 50 | Translated by ChatGPT 5