Here are some terms

$a_1 = k, a_2 = 2k + 1, a_3 = 3k + 2$ $a_4 = 8k + 7, a_5 = 10k + 9, a_6 = 12k + 11, a_7 = 14k + 13, a_8 = 16k + 15$ $a_9 = 27k + 26, a_{10} = 30k + 29, a_{11} = 33k + 32, a_{12} = 36k + 35, a_{13} = 39k + 38, a_{14} = 42k + 41, a_{15} = 45k + 44$

We can see that for blocks for size $3, 5, 7, \ldots$ , the Common difference of coefficient of $k$ and constant term is constant and equal to coefficient of $k$ in $a_{\sqrt{n}}$ . It is also obvious as for consecutive odd ranges, square root is same number.

Above Question Can Be Solved By Breaking It into blocks of size $3, 5, 7 \ldots$ respectively. This results in a time complexity $O(\sqrt{n})$

Here is the code:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91

#include <bits/stdc++.h>
using namespace std;

#define ll long long int
#define rep(i,n) for(ll i=0; i<n; ++i)
#define repi(i,a,n) for(ll i=a; i<n; ++i)
#define repii(i,a,n,b) for(ll i=a; i<n; i+=b)

// Defining constants
#define mod 1000000007

ll power(ll a, ll b) 
{
    ll ans = 1;
    while(b) {
        if(b%2) ans = (ans*a)%mod;
        a = (a*a)%mod;
        b = b>>1;
    }
    return ans;
}

int main()
{
    // For Fast I/O
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    ll n, k;
    cin>>n>>k;

    ll s = sqrt(n);
    ll index = 1;

    ll ans = 0, a[2 * s][2];

    rep(i, 2 * s)
    {
        a[i][0] = 0;
        a[i][1] = 0;
    }

    a[1][0] = 1;
    a[1][1] = 1;

    repi(i, 1, s + 1)
    {
        ll firstterm, commondiff;

        ll ind = sqrt(index);
        ll indk = sqrt(ind);

        commondiff = (a[indk][0] + a[indk][1] * (ind - (indk * indk))) % mod;
        firstterm = (commondiff * index) % mod;

        ll totalterms = (2 * i + 1) % mod;

        ans = (ans + ((k * (totalterms * ((2 * firstterm + (totalterms - 1) * commondiff) % mod)) % mod) % mod) * power(2, mod - 2)) % mod;

        ans = (ans + ((totalterms * ((2 * (firstterm - 1) + (totalterms - 1) * commondiff) % mod)) % mod) * power(2, mod - 2)) % mod;

        a[i][0] = firstterm % mod;
        a[i][1] = commondiff % mod;

        index += 2 * i + 1;
    }

    cout<<ans<<"\n";

    // Brute Force Test Code Below(For Smaller Values)

    // ll b[s + 1];
    // b[1] = k;

    // ans = 0;

    // repi(i, 1, n + 1)
    // {
    //     ll sq = sqrt(i), k;

    //     k = (i * b[sq]) + (i - 1);
    //     ans = (ans + k) % mod;

    //     if(i <= s)
    //     b[i] = k;
    // }

    // cout<<ans<<"\n \n";

}

1
2

Input:
9999999999 7273682

1
2

Output:
141763014