Ideone.com

fork download

copy

#include<bits/stdc++.h>
#define fastio {ios_base::sync_with_stdio(false);cin.tie(NULL);}
//#define ll   long long int
#define all(u) sort(u.begin(),u.end())
#define nxt(u) next_permutation(u.begin(),u.end())
#define rev(u) reverse(u.begin(),u.end())
#define cinv(u) for(auto &it : u) cin >> it;
#define pb push_back
#define Which would be worse
#define siz(st) st.size()
#define nl "\n"
#define yes cout<<"Yes"<<"\n"
#define no cout<<"No"<<"\n"
#define pii  pair < int , int >
#define ss second
#define ff first
#define PI acos(-1.0)
#define v vector
#define For(s , e , k) for(int i = s ; i <= (int)e ; i += k)
#define print(s , e , k , ar) for(int i = s ; i <= (int)e ; i += k) cout << ar[i] << " \n"[i == e]
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
//using namespace __gnu_pbds;
typedef long long ll;
template <class type1>
//using ordered_multiset = tree <type1, null_type, less_equal <type1>, rb_tree_tag, tree_order_statistics_node_update>;
#ifndef ONLINE_JUDGE
#include "template.h"
#endif
const int fx[]={-1,0,1,0};
const int fy[]={0,1,0,-1};
//cout<<"Case "<<t<<": "<<ans<<endl;
//priority_queue <ll, vector<ll>, greater<ll> > pq;//soto theke boro
//cout<<setprecision(10)<<fixed;
// ll id=lower_bound(de.begin(),de.end())-de.begin();
/*remainder extra space*/
//v < v < int > > ar(n + 1 , v < int > (m + 1 , 0));
const ll M = 1e3  ,N = 1e6 + 3 , mod = 1e9 + 7 , N1 = 1e6 ;
//Hope for the best , but prepare for the worst
 
int prime[M+10];
vector< int > br , pr(N) , ar(N)  ;
vector < ll > cal(N1);
 
ll bigmod(ll base ,ll power ,ll mod)
{
    if(power==0)
    return 1;
    else if(power%2==1)
    {
        ll a=(base%mod);
        ll b=bigmod(base,power-1,mod);
        return (a*(b%mod))%mod;
 
    }
    else
    {
        ll a=bigmod(base,power/2,mod);
        return (a*a)%mod;
    }
 
 
}
 
ll ok(ll n){
   return (((n + 1)  * 1ll* (n + 2) ) / 2) % mod;
}
 
void sieve()
{
   for(int i = 2;i <=M;i++)
    {
        if(prime[i]==0)
        {
                for(ll j=i+i;j<=M;j+=i)
                prime[j]=1;
                br.push_back(i);
        }
 
    }
    for(int i = 1 ; i <= N1 ; i++){
        ll r  = ok(i);
        cal[i] = bigmod(r , mod - 2 , mod);
    }
 
    pr[1] = 1 ;
    ll ans = 1 ;
 
    for(int i = 2 ; i < N ; i++){
       int x = i ;
       v < pii > pa ;
 
       for(int j = 0;j <br.size() && br[j] * br[j] <= x;j++){
           int cnt = 0 ;
           while(x % br[j] == 0){
             x /= br[j];
             cnt++;
           } 
           pa.pb({br[j] , cnt});
 
       }
       if(x > 1){
          pa.pb({x , 1});
 
       }
 
 
       for(auto &it : pa){
         ll val = it.ff;
         ll  oc = it.ss ;
        // cout << i << ' ' << val << ' ' << oc << endl;
 
         if(!ar[val]){
              ll r = ok(oc);
              ans = (ans *  1ll *  r) % mod ;
              ans = ans % mod ;
              ar[val] = oc ;
         }
         else {
 
              ll op = cal[ar[val]];
              ans = (ans *1ll *  op) % mod ;
 
              ar[val] += oc ;
              ll r = ok(ar[val]);
              ans = (ans *1ll *  r) % mod ;
              ans = ans % mod ;
 
         }
       }
 
       pr[i] = ans ;
    }
 
}
void solve(){
   while(1){
     int x ;
     cin >> x ;
     if(x == 0) break ;
     cout << pr[x] << nl;
    } 
}
int  main(){
   fastio;
   int T = 1 ;
   //cin >> T;
    sieve();
   while(T--)
   solve();
}

I2luY2x1ZGU8Yml0cy9zdGRjKysuaD4KI2RlZmluZSBmYXN0aW8ge2lvc19iYXNlOjpzeW5jX3dpdGhfc3RkaW8oZmFsc2UpO2Npbi50aWUoTlVMTCk7fQovLyNkZWZpbmUgbGwgICBsb25nIGxvbmcgaW50CiNkZWZpbmUgYWxsKHUpIHNvcnQodS5iZWdpbigpLHUuZW5kKCkpCiNkZWZpbmUgbnh0KHUpIG5leHRfcGVybXV0YXRpb24odS5iZWdpbigpLHUuZW5kKCkpCiNkZWZpbmUgcmV2KHUpIHJldmVyc2UodS5iZWdpbigpLHUuZW5kKCkpCiNkZWZpbmUgY2ludih1KSBmb3IoYXV0byAmaXQgOiB1KSBjaW4gPj4gaXQ7CiNkZWZpbmUgcGIgcHVzaF9iYWNrCiNkZWZpbmUgV2hpY2ggd291bGQgYmUgd29yc2UKI2RlZmluZSBzaXooc3QpIHN0LnNpemUoKQojZGVmaW5lIG5sICJcbiIKI2RlZmluZSB5ZXMgY291dDw8IlllcyI8PCJcbiIKI2RlZmluZSBubyBjb3V0PDwiTm8iPDwiXG4iCiNkZWZpbmUgcGlpICBwYWlyIDwgaW50ICwgaW50ID4KI2RlZmluZSBzcyBzZWNvbmQKI2RlZmluZSBmZiBmaXJzdAojZGVmaW5lIFBJIGFjb3MoLTEuMCkKI2RlZmluZSB2IHZlY3RvcgojZGVmaW5lIEZvcihzICwgZSAsIGspIGZvcihpbnQgaSA9IHMgOyBpIDw9IChpbnQpZSA7IGkgKz0gaykKI2RlZmluZSBwcmludChzICwgZSAsIGsgLCBhcikgZm9yKGludCBpID0gcyA7IGkgPD0gKGludCllIDsgaSArPSBrKSBjb3V0IDw8IGFyW2ldIDw8ICIgXG4iW2kgPT0gZV0KLy8jaW5jbHVkZSA8ZXh0L3BiX2RzL2Fzc29jX2NvbnRhaW5lci5ocHA+Ci8vI2luY2x1ZGUgPGV4dC9wYl9kcy90cmVlX3BvbGljeS5ocHA+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7Ci8vdXNpbmcgbmFtZXNwYWNlIF9fZ251X3BiZHM7CnR5cGVkZWYgbG9uZyBsb25nIGxsOwp0ZW1wbGF0ZSA8Y2xhc3MgdHlwZTE+Ci8vdXNpbmcgb3JkZXJlZF9tdWx0aXNldCA9IHRyZWUgPHR5cGUxLCBudWxsX3R5cGUsIGxlc3NfZXF1YWwgPHR5cGUxPiwgcmJfdHJlZV90YWcsIHRyZWVfb3JkZXJfc3RhdGlzdGljc19ub2RlX3VwZGF0ZT47CiNpZm5kZWYgT05MSU5FX0pVREdFCiNpbmNsdWRlICJ0ZW1wbGF0ZS5oIgojZW5kaWYKY29uc3QgaW50IGZ4W109ey0xLDAsMSwwfTsKY29uc3QgaW50IGZ5W109ezAsMSwwLC0xfTsKLy9jb3V0PDwiQ2FzZSAiPDx0PDwiOiAiPDxhbnM8PGVuZGw7Ci8vcHJpb3JpdHlfcXVldWUgPGxsLCB2ZWN0b3I8bGw+LCBncmVhdGVyPGxsPiA+IHBxOy8vc290byB0aGVrZSBib3JvCi8vY291dDw8c2V0cHJlY2lzaW9uKDEwKTw8Zml4ZWQ7Ci8vIGxsIGlkPWxvd2VyX2JvdW5kKGRlLmJlZ2luKCksZGUuZW5kKCkpLWRlLmJlZ2luKCk7Ci8qcmVtYWluZGVyIGV4dHJhIHNwYWNlKi8KLy92IDwgdiA8IGludCA+ID4gYXIobiArIDEgLCB2IDwgaW50ID4gKG0gKyAxICwgMCkpOwpjb25zdCBsbCBNID0gMWUzICAsTiA9IDFlNiArIDMgLCBtb2QgPSAxZTkgKyA3ICwgTjEgPSAxZTYgOwovL0hvcGUgZm9yIHRoZSBiZXN0ICwgYnV0IHByZXBhcmUgZm9yIHRoZSB3b3JzdAogCmludCBwcmltZVtNKzEwXTsKdmVjdG9yPCBpbnQgPiBiciAsIHByKE4pICwgYXIoTikgIDsKdmVjdG9yIDwgbGwgPiBjYWwoTjEpOwoKbGwgYmlnbW9kKGxsIGJhc2UgLGxsIHBvd2VyICxsbCBtb2QpCnsKICAgIGlmKHBvd2VyPT0wKQogICAgcmV0dXJuIDE7CiAgICBlbHNlIGlmKHBvd2VyJTI9PTEpCiAgICB7CiAgICAgICAgbGwgYT0oYmFzZSVtb2QpOwogICAgICAgIGxsIGI9YmlnbW9kKGJhc2UscG93ZXItMSxtb2QpOwogICAgICAgIHJldHVybiAoYSooYiVtb2QpKSVtb2Q7CgogICAgfQogICAgZWxzZQogICAgewogICAgICAgIGxsIGE9YmlnbW9kKGJhc2UscG93ZXIvMixtb2QpOwogICAgICAgIHJldHVybiAoYSphKSVtb2Q7CiAgICB9CgoKfQoKbGwgb2sobGwgbil7CiAgIHJldHVybiAoKChuICsgMSkgICogMWxsKiAobiArIDIpICkgLyAyKSAlIG1vZDsKfQoKdm9pZCBzaWV2ZSgpCnsKICAgZm9yKGludCBpID0gMjtpIDw9TTtpKyspCiAgICB7CiAgICAgICAgaWYocHJpbWVbaV09PTApCiAgICAgICAgewogICAgICAgICAgICAgICAgZm9yKGxsIGo9aStpO2o8PU07ais9aSkKICAgICAgICAgICAgICAgIHByaW1lW2pdPTE7CiAgICAgICAgICAgICAgICBici5wdXNoX2JhY2soaSk7CiAgICAgICAgfQoKICAgIH0KICAgIGZvcihpbnQgaSA9IDEgOyBpIDw9IE4xIDsgaSsrKXsKICAgICAgICBsbCByICA9IG9rKGkpOwogICAgICAgIGNhbFtpXSA9IGJpZ21vZChyICwgbW9kIC0gMiAsIG1vZCk7CiAgICB9CiAgIAogICAgcHJbMV0gPSAxIDsKICAgIGxsIGFucyA9IDEgOwoKICAgIGZvcihpbnQgaSA9IDIgOyBpIDwgTiA7IGkrKyl7CiAgICAgICBpbnQgeCA9IGkgOwogICAgICAgdiA8IHBpaSA+IHBhIDsKCiAgICAgICBmb3IoaW50IGogPSAwO2ogPGJyLnNpemUoKSAmJiBicltqXSAqIGJyW2pdIDw9IHg7aisrKXsKICAgICAgICAgICBpbnQgY250ID0gMCA7CiAgICAgICAgICAgd2hpbGUoeCAlIGJyW2pdID09IDApewogICAgICAgICAgICAgeCAvPSBicltqXTsKICAgICAgICAgICAgIGNudCsrOwogICAgICAgICAgIH0gCiAgICAgICAgICAgcGEucGIoe2JyW2pdICwgY250fSk7CiAgICAgICAgICAgCiAgICAgICB9CiAgICAgICBpZih4ID4gMSl7CiAgICAgICAgICBwYS5wYih7eCAsIDF9KTsKICAgICAgICAgCiAgICAgICB9CiAgICAgICAKICAgICAgIAogICAgICAgZm9yKGF1dG8gJml0IDogcGEpewogICAgICAgICBsbCB2YWwgPSBpdC5mZjsKICAgICAgICAgbGwgIG9jID0gaXQuc3MgOwogICAgICAgIC8vIGNvdXQgPDwgaSA8PCAnICcgPDwgdmFsIDw8ICcgJyA8PCBvYyA8PCBlbmRsOwogICAgICAgICAKICAgICAgICAgaWYoIWFyW3ZhbF0pewogICAgICAgICAgICAgIGxsIHIgPSBvayhvYyk7CiAgICAgICAgICAgICAgYW5zID0gKGFucyAqICAxbGwgKiAgcikgJSBtb2QgOwogICAgICAgICAgICAgIGFucyA9IGFucyAlIG1vZCA7CiAgICAgICAgICAgICAgYXJbdmFsXSA9IG9jIDsKICAgICAgICAgfQogICAgICAgICBlbHNlIHsKICAgICAgICAgICAgICAKICAgICAgICAgICAgICBsbCBvcCA9IGNhbFthclt2YWxdXTsKICAgICAgICAgICAgICBhbnMgPSAoYW5zICoxbGwgKiAgb3ApICUgbW9kIDsKCiAgICAgICAgICAgICAgYXJbdmFsXSArPSBvYyA7CiAgICAgICAgICAgICAgbGwgciA9IG9rKGFyW3ZhbF0pOwogICAgICAgICAgICAgIGFucyA9IChhbnMgKjFsbCAqICByKSAlIG1vZCA7CiAgICAgICAgICAgICAgYW5zID0gYW5zICUgbW9kIDsKCiAgICAgICAgIH0KICAgICAgIH0KICAgICAgIAogICAgICAgcHJbaV0gPSBhbnMgOwogICAgfQoKfQp2b2lkIHNvbHZlKCl7CiAgIHdoaWxlKDEpewogICAgIGludCB4IDsKICAgICBjaW4gPj4geCA7CiAgICAgaWYoeCA9PSAwKSBicmVhayA7CiAgICAgY291dCA8PCBwclt4XSA8PCBubDsKICAgIH0gCn0KaW50ICBtYWluKCl7CiAgIGZhc3RpbzsKICAgaW50IFQgPSAxIDsKICAgLy9jaW4gPj4gVDsKICAgIHNpZXZlKCk7CiAgIHdoaWxlKFQtLSkKICAgc29sdmUoKTsKfQ==

Runtime error #stdin #stdout 2.37s 19076KB

stdin

copy

Standard input is empty

stdout

copy

https://ideone.com/xMoINo

language:

C++ (gcc 8.3)

created:

visibility:

secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!

Discover > Sphere Engine API

Discover > IDE Widget

Choose your language