Not all who wander are lost.
Perhaps it's just taking a walk, or perhaps it's for escaping from something. Roundgod temporarily left the city he used to live in and headed to a boundless forest.
Roundgod then began to wander in the forest. If we consider the forest as a two-dimensional Cartesian plane, then Roundgod starts from (0,0), and each time he chooses one of the four directions uniformly at random and moves one step forward(i.e.,the possible changes of Roundgod's coordinates are (−1,0),(1,0),(0,−1),(0,1)). After Roundgod took n steps, he stopped, in a trance, realizing that he had been wandering for too long and that it was time to return to his casual life. Now there's only one remaining problem that he wonders: During the n steps he moved, how far he was from the starting point? As Roundgod has forgotten the moves he has taken, he only wants to know the expected answer for all his possible routes.
Formally, Roundgod starts from (0,0), each time chooses one of the four directions uniformly at random and moves one step forward. You should calculate, among all his 4n possible routes, the expected maximum Manhattan distance between any position on his route and (0,0).
Specifically, the Manhattan distance between two points p1=(x1,y1) and p2=(x2,y2) in the Cartesian plane is defined as d(p1,p2)=|x1−x2|+|y1−y2|. Also, for any prime modular 108≤MOD≤109+7, we can prove that the answer can be written as a fraction P/Q, where P and Q are coprime integers and Q≢0(modMOD). You need to output P⋅Q−1(modMOD) as the answer, where Q−1(modMOD) represents the modular inverse of Q with respect to MOD.