All submissions for this problem are available.**An act of evil passed down a generation would result in a nation of disunity.** It is hard to imagine how one so malicious can attempt to attain the status of saviour. Boundless ruin and torment has left many a world in ruin. Thanos has invaded Thor's ship, and aided by his children, extinguishes the once vigorously burning candle of Heimdall's life and snatches the Power Stone. Overcome with rage, Thor vows to vanquish Thanos once and for all. Thor's Storm Breaker axe can be described as a square $N$ by $N$ grid mounted on the strong wooden support(that Groot provided, of course). By attempting last year's questions, Thanos has gained access to Batman's superior technology, and his metal armour can detect and absorb any weapon impacts, which render him almost invincible. Thor uses only three of the strongest materials, **diamond**,**sapphire** and **tungsten** to build his axe. His axe is subdivided into **N2** **1 x 1** blocks. Thanos' armour is faulty and $fails$ to absorb impact under the following conditions: 1) Every block of the axe is made of **any one** of the 3 materials. 2) **No** row or column of blocks is made of only one material. To deliver the decisive strike, Thor wonders in how many ways he can design his axe, such that he can vanquish Thanos with one powerful strike. Two designs are considered to be different if at least one of the blocks is made of a different material in both axes. Stand tall, Heimdall, your sacrifice shall not be in vain. ###Input Format: The only line of input consists of $N$, the dimension of the Storm Breaker. ###Output Format: Print a single line for each test case, the number of ways to design the axe **modulo** **109 + 7**. ###Constraints: $1$ $\leq$ $N$ $\leq$ **106** ###Sample input: 1 ###Sample output: 0 ###Explanation: It is clear that no valid axe can be designed as per the conditions mentioned.
|Time Limit:||5 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6|
Fetching successful submissions