/**

    • struct Point {
    • int x;
    • int y;
    • };
  • */

class Solution
{
uint64_t Modp = 1000000007;
uint32_t Inv(uint64_t num)
{
uint32_t result = 1, Power = 1000000005;
while (Power > 0)
{
if (Power & 1)
result = result * num % Modp;
Power >>= 1;
num = num * num % Modp;
}
return result;
}
Point TwoTimesPoint(Point P)
{
Point R;
uint64_t k = (3 * (uint64_t)P.x * P.x + 1) % Modp * Inv(2 * P.y % Modp) % Modp;
R.x = (k * k + 2 * Modp - 2 * P.x) % Modp;
R.y = (k * (P.x + Modp - R.x) + Modp - P.y) % Modp;
return R;
}
Point TwoPointsAdd(Point P, Point Q)
{
Point R;
uint64_t k = (Q.y + Modp - P.y) * Inv((Q.x + Modp - P.x) % Modp) % Modp;
R.x = (k * k % Modp + 2 * Modp - P.x - Q.x) % Modp;
R.y = (k * (P.x + Modp - R.x) + Modp - P.y) % Modp;
return R;
}

public:
/**

  • @param P Point类
  • @param n int整型
  • @return Point类
  • /
    Point NTimesPoint(Point P, int n)
    {
    // write code here
Point PointTimes[30] = {P}, NP;
uint8_t NBin[30], Leath = 0, Flag = 0;
for (; n > 0; Leath += 1)
{
    NBin[Leath] = n & 1;
    n >>= 1;
}
for (uint8_t i = 1; i < Leath; i += 1)
    PointTimes[i] = TwoTimesPoint(PointTimes[i - 1]);
while (!NBin[Flag++])
    ;
NP = PointTimes[Flag - 1];
for (uint8_t i = Flag; i < Leath; i++)
{
    if (NBin[i])
        NP = TwoPointsAdd(NP, PointTimes[i]);
}
return NP;
    }
    };