一.闲话

哎，之前开C的时候，发现有点计算几何的味道，就打算放放，开D，结果发现D是数论，于是就决定搞出来了。然后一直Wa。。。debug了几个小错误后，实在没发现错了。。。结果后面rejudge就过了？？？/xk

二.题解

首先，这题几个结论:

1.我们不会选两个相同的数（除了用1来补满和以外）

这个证明就不说了，很naive

2.我们放的数一定是放的一个质数的k次方。

为啥呢？

我们分析下，假如我们放了一个数那么，其实，等价于我们分别放了两个数(甚至我们单独放这两个数的答案可能还要大点。。。)，然后，由于恒成立，所以贪心来看，我们用更小的代价，换到了更大的收益，那么要获得最大收益肯定是用的这个策略。所以结论成立。

3.如果我们选了,那么我们必然选了

证明也很简单，如果我们有一个没选，那么，我们将k次换成那个后，贡献不变，代价减小了。所以要选的话必然是连续选的。

4.

和上面的分析方式类似，若，那么我们取个取个，与现在的取法的答案是一样的，但是这种取法的代价明显小于现在的取法。

有了上述几个结论后，做法就很显然了，类比于做求1-n中公约数最多的数那个做法，我们dfs枚举每个质数取几个就行了。每次将当前答案取最大即可。

那么，如何计算代价呢？

一开始肯定是1(空集的一个)。

那么，假如加入前的答案为x,我们加入了一组后，我们发现，对于原来的每个lcm，都一定与现在的这个数互质，那么对于每个lcm,就会多出个不同的分支(分别加入这几个中其中一个)。

所以现在的答案就变成了那么，我们如果加入多个的次方怎么办？其实还是等价于我们只加入最大的那个而已。（因为有空集，所以答案完备）

所以代码就很好打了。

那么，又来了一个问题。

我们的答案是要取模的，取模后大小关系会变化啊？怎么办呢？有几种办法，我直接说下我naive的做法吧。我直接上一个高精，然后最后输出答案的时候取模即可。

但是，打普通高精会TLE，那么，压个位就好了。（最好多压几位，跑得快点）

代码:

#pragma GCC optimize(3,"inline","Ofast")
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+1,mod=1e9+7,inf=2e9;
const long long T=1e15;
int a[N];
int zhi[N],e;bool f[N];int n;
int sav[N];
struct node{
    long long a[6];
}ans;
inline node max(node x,node y){
    for(int i=5;~i;--i){
        if(x.a[i]!=y.a[i]){
            return x.a[i]>y.a[i]?x:y;
        }
    }
    return x;
}
inline void sai(){
    for(int i=2;i<N;++i){
        if(!f[i]){
            zhi[++e]=i;
        }
        for(int j=1;j<=e;++j){
            if(i*zhi[j]>=N)break;
            f[i*zhi[j]]=1;
            if(i%zhi[j]==0)break;
        }
    }
}
inline node operator*(node x,int y){
    for(int i=0;i<=5;++i)x.a[i]*=y;
    for(int i=0;i<5;++i)x.a[i+1]+=x.a[i]/T,x.a[i]%=T;
    return x;
}
inline int operator%(node x,int y){
    __int128 now=0;
    for(int i=5;~i;--i){
        now=(now*T)%y;now=(now+x.a[i])%y;
    }
    int fow=now;
    return fow;
}
inline void dfs(int now,int sum,int x,node res){//枚举其次即可
    ans=max(ans,res);
    int lon=1,tot=0;
    for(int i=1;i<=x;++i){
        lon*=zhi[now];tot+=lon;
        if(sum+tot>n)break;
        sav[now]=i;
        //将zhi[now]^1...zhi[now]^i添加进去
        //每个都和之前的所有互质，那么，单独来看，即添加了res*i个
        node tp=res*(i+1);
        dfs(now+1,sum+tot,i,tp);
    }
}
node st;
signed main(){
    sai();
    scanf("%lld",&n);
    if(n==1){
        puts("1");
        return 0;
    }
    //添加的必然为pi^k
    st.a[0]=1;
    dfs(1,0,inf,st);
    int ant=ans%mod;
    printf("%lld",ant);
    system("pause");
    return 0;
}