from functools import *
import math

n=10**7
mod=11**8

@cache
def Z(m):
    if m<=3:
        return (0,1,2,4)[m]
    j=math.isqrt(m)  
    res=m*(m+1)//2-sum(Z(m//i) for i in range(2,j+1))
    k=m//j
    while k>0:
        i=m//k
        res-=(i-j)*Z(k)
        j=i
        k-=1   
    return res

s=[1]*(n//2+2)
p=2
while p<=n//2:
    q=p
    while q<=n//2:
        s[q]=p
        q+=p
    p+=1
    while s[p]>1:
        p+=1

t=[1]*(n+2)
p=2
while p<=n:
    q=p
    while q<=n:
        t[q]*=(p-1)
        q+=p
    r=p*p
    while r<=n:
        q=r
        while q<=n:
            t[q]*=p
            q+=r
        r*=p   
    p+=1            
    while t[p]>1:
        p+=1

lines=[n+1-i for i in range(n+1)]
lines[1]=Z(n)
for i in range(2,n//2+1):
    k=i
    pos=[]
    neg=[]
    while k>1:
        p=s[k]
        while k%p==0:
            k//=p
        x=len(neg)
        neg.append(p)
        for q in pos:
            neg.append(p*q)
        for j in range(x):
            pos.append(p*neg[j])
        
    for d in range(2,n//i+1):
        r=n-d*i
        lines[d]+=r+sum(r//x for x in pos)-sum(r//x for x in neg)          

h=3*sum(lines[d]*t[d] for d in range(1,n+1))
a=pow(2,h,mod)
c=0
p=pow(2,h-lines[1],mod)
x=lines[1]
for d in range(1,n+1):
    y=lines[d]
    p=p*pow(2,x-y,mod)%mod
    c+=t[d]*(a-p)%mod  
    x=y     
print((pow(2,2*h+1,mod)-1-6*c)%mod)