I said that the answer polynomial is (59x^5 - 11x^3) / 3, but actually it's same modulo to 666666691x^5 + 333333332x^3 (let this the answer polynomial).

It seems like the sample input only provides (x,y)=(1,16),(3,4680),(5,61000), but it's not true. Because:

1. You can also get (x, y) = (0, 0), obviously.

2. Doing "newton's polynomial interpolation" with mod 1000000007, you can add (x, y) = (12345, 598011702), (999993007, 763641672) from sample input (999993007 is equal to 1000000000000 mod 1000000007).

Now you have 6 points! So you can get the answer polynomial!!!!!

Also, the code of newton's polynomial interpolation (my library) is this:

vector<int> interpolation(vector<int> x,]]>intm) {intn = x.size() - 1; vector<int> inv(n + 1); inv[1] = 1;for(inti = 2; i <= n; i++) inv[i] = 1LL * inv[m % i] * (m - m / i) % m; vector<vector<int> > dp(n + 1, vector<int>(n + 2));for(inti = 0; i <= n; i++) dp[i][i + 1] = x[i];for(inti = 2; i <= n + 1; i++) {for(intr = i; r <= n + 1; r++) {intl = r - i; dp[l][r] = 1LL * (dp[l + 1][r] - dp[l][r - 1] + m) * inv[i - 1] % m; } } vector<int> ret(n + 1); ret[0] = x[0]; vector<int> mul({ 1 });for(inti = 0; i < n; i++) { vector<int> mul2(i + 2, 0);for(intj = 0; j <= i; j++) mul2[j + 1] = mul[j];for(intj = 0; j <= i; j++) mul2[j] = (mul2[j] + 1LL * (m - i) * mul[j]) % m; mul = mul2;for(intj = 0; j <= i + 1; j++) ret[j] = (ret[j] + 1LL * mul[j] * dp[0][i + 2]) % m; }returnret; }

https://www.wolframalpha.com/input/?i=interpolating+polynomial+%7B0,+0%7D,%7B1,+16%7D,%7B2,+600%7D,%7B3,+4680%7D,%7B4,+19904%7D,%7B5,+61000%7D

The statement only provides 4 points (without module): (0, 0), (1, 16), (3, 4680), (5, 61000). Someone did the following thing:

https://community.topcoder.com/stat?c=problem_solution&cr=40509829&rd=17027&pm=14738

Which is basically writing a brute force solution, getting the missing values for n=2 (600) and n=4 (19904) and solving the polynomial interpolation using wolfram alpha (or whatever online solver you want) and afterwards implementing the equation, which is constant. This is a nice piece of art.]]>

There are O(n^2) vertices so there are O(n^4) pairs of vertices. The distance between two vertices is O(n), so you can guess that the answer is polynomial which degree = 5.

Then, find the answer for n=0,1,2,3,4,5. Finally use "polynomial interpolation" and get the answer = (59n^5 - 11n^3) / 3. If you check for n=6,7,8,9,10, you can see that this polynomial is correct.]]>

2) between-block path:

I label the block from topmost 1, leftmost 2, mid 3, rightmost 4, and the remain 5.

i) calc the path 1-2 , and the result is same to 2-4, 4-5 ,5-1

ii) calc the path 1-4 , and the result is same to 2 - 4

iii) calc the path 1-3 , and the result is same to 2-3 4-3 5-3

when calculating the path 1-2 , you can only consider the bottom-left of 1 and the top-right of 2, and the in-block point to the bottom-left....

I though there may be a more easier solution using InclusionÃ¢ÂÂexclusion principle...

have a good luck.....: )]]>

Please help.]]>