1061C - Multiplicity - CodeForces Solution

/*---------JAI HO GURUDEV---------*/ 

#include<bits/stdc++.h>
using namespace std;
#define ll long long 
#define f(i,n) for(ll i=0;i<n;i++)
#define fast cin.tie(0), cout.tie(0), cin.sync_with_stdio(0), cout.sync_with_stdio(0);
#define f1(i,n) for(ll i=n;i>=0;i--)
#define forr(i,a,b) for(ll i=a;i<b;i++)
#define forr1(i,a,b) for(ll i=a;i>=a;i--)
#define rep(i,a,b)  for(int i=a;i<b;i++)
#define sor(vec) sort(vec.begin(),vec.end())
#define asor(ar) sort(ar,ar+ar.size());
#define rsor(vec) sort(vec.rbegin(),vec.rend());
#define dbg(var) cout<<#var<<"="<<var<<" "
#define vl vector<ll>
#define yes cout << "YES"<< endl;
#define no cout << "NO"<< endl;
#define out(n) cout << n << endl;
#define num(n) ll n; cin >> n;
#define mxe(v)  *max_element(v.begin(),v.end())     // find max element in vector
#define mne(v)  *min_element(v.begin(),v.end())     // find min element in vector
#define pb push_back
#define so(arr,n) sort(arr,arr+n) 
const ll MOD = 998244353;
const ll mod= 1000000007;
const ll N = 1e3 + 1;
vector<int>adj[N];
vector<bool>vis(N,false);
 

 int INF=INT_MAX;


// ================================== take ip/op like vector,pairs directly!==================================
template<typename typC,typename typD> istream &operator>>(istream &cin,pair<typC,typD> &a) { return cin>>a.first>>a.second; }
template<typename typC> istream &operator>>(istream &cin,vector<typC> &a) { for (auto &x:a) cin>>x; return cin; }
template<typename typC,typename typD> ostream &operator<<(ostream &cout,const pair<typC,typD> &a) { return cout<<a.first<<' '<<a.second; }
template<typename typC,typename typD> ostream &operator<<(ostream &cout,const vector<pair<typC,typD>> &a) { for (auto &x:a) cout<<x<<'\n'; return cout; }
template<typename typC> ostream &operator<<(ostream &cout,const vector<typC> &a) { int n=a.size(); if (!n) return cout; cout<<a[0]; for (int i=1; i<n; i++) cout<<' '<<a[i]; return cout; }
// ===================================END Of the input module ==========================================
 
// ====================================start of the segment tree=========================================
class STree{
private:
    vector<ll> tree;
    int n;
    ll sum(ll v, ll tl, ll tr, ll l, ll r) {      
        if (l > r) return 0;
        if (l == tl && r == tr) return tree[v];
        
        ll tm = (tl + tr) / 2;
        return sum(v*2, tl, tm, l, (ll)min(r, tm))  + sum(v*2+1, tm+1, tr, (ll)max(l, tm+1), r);
    }
    ll minim(ll v,ll tl,ll tr,ll l,ll r)
    {
    if (tr<l || tl>r) return INT_MAX;
    if(tl>=l && tr<=r)
    return tree[v];
        
        ll tm = (tl + tr) / 2;
        return min(minim(v*2, tl, tm, l, r), minim(v*2+1, tm+1, tr, l, r));    
    }
    void buildTree(vector<ll>& a,ll tl, ll tr,ll v=1){
        if(tl>tr) return;
        if(tl==tr){
            tree[v]=a[tl];
            return;
        }
 
        ll mid=(tl+tr)/2;
        buildTree(a,tl,mid,v*2);
        buildTree(a,mid+1,tr,v*2+1);
        tree[v]=tree[v*2]+tree[v*2+1]; //sum
        tree[v]=min(tree[2*v],tree[2*v+1]);//  minimum
    }
    void update(ll idx,ll val,ll v,ll tl,ll tr){
        if(tl>tr) return;
        if(idx<tl || idx>tr)  return;     //not in the current range
        if(tl==tr){
            tree[v]=val;
            return;
        }
        ll tmid=(tl+tr)/2;
        update(idx,val,v*2,tl,tmid);
        update(idx,val,v*2+1,tmid+1,tr);
        tree[v]=tree[v*2]+tree[v*2+1];
    }
public:
    STree(ll sz,vector<ll>& vec){
        n=sz;
        tree.assign(sz*4,0);
        buildTree(vec,0,n-1);
    }
 
    ll getSum(int l,int r){
        return sum(1,0,n-1,l,r);         // call the function!
    }
    void update(ll idx,ll val){     // v is the new value!
        update(idx,val,1,0,n-1);
    }
    void printTree(vector<ll>& v){
        cout<<v<<"\n";
    }
 
};
// ========================================= Segment tree ends here====================================

// FERMAT'S LITTLE THEOREM
ll fastpow(ll a, ll b,ll Mod){
    ll res = 1;
    while(b > 0){
        if(b&1)
            res = (res * a) % Mod;
        a = (a * a) % Mod;
        b >>= 1;
    }
    return res;
}
class DisjointSet
{
    vector<int> rank,parent;
public: 
    DisjointSet(int n)
    {
        parent.resize(n+1);
        rank.resize(n+1,0);
        for(int i=0;i<=n;i++)
            parent[i]=i;
     }
     int ul_parent(int u)
     {
   if(parent[u]==u)
    return u;
else
    return parent[u]=ul_parent(parent[u]);
     }
     void findUnionByRank(int u,int v)
     {
        int ul_u=ul_parent(u);
        int ul_v=ul_parent(v);
        if(ul_u==ul_v)
            return;
        else if(rank[ul_u]<rank[ul_v])
            parent[ul_u]=ul_v;
        else if(rank[ul_v]<rank[ul_u])
        {
            parent[ul_v]=ul_u;
        }
        else
        {
            rank[ul_u]++;
            parent[ul_v]=ul_u;
        }
     }


};

vector<int>  SieveOfEratosthenes(int n)
{
    // Create a boolean array "prime[0..n]" and initialize
    // all entries it as true. A value in prime[i] will
    // finally be false if i is Not a prime, else true.
    bool prime[n + 1];
    memset(prime, true, sizeof(prime));
 
    for (int p = 2; p * p <= n; p++) {
        // If prime[p] is not changed, then it is a prime
        if (prime[p] == true) {
            // Update all multiples of p greater than or
            // equal to the square of it numbers which are
            // multiple of p and are less than p^2 are
            // already been marked.
            for (int i = p * p; i <= n; i += p)
                prime[i] = false;
        }
    }
 vector<int> v;
    // Print all prime numbers
    for (int p = 2; p <= n; p++)
        if (prime[p])
            v.pb(p);
        return v;
}
int position(ll x)
{
    int c=0;
    while(x!=0)
    {
        c++;
        x=x>>1;
    }
    return c;
}
bool compare(pair<int,int> a,pair<int,int> b)
{
    if(a.first==a.second)
    return abs(a.second-b.second)>1;
else
    return a.first>b.first;
}
bool subsetSumUtil(int ind, int target, vector<int>& arr, vector<vector<int>> &dp){
    if(target==0)
        return true;
    
    if(ind == 0)
        return arr[0] == target;
    
    if(dp[ind][target]!=-1)
        return dp[ind][target];
        
    bool notTaken = subsetSumUtil(ind-1,target,arr,dp);
    
    bool taken = false;
    if(arr[ind]<=target)
        taken = subsetSumUtil(ind-1,target-arr[ind],arr,dp);
        
    return dp[ind][target]= notTaken||taken;
}
int ask(int l, int r) {
    cout << "? " << l << ' ' << r << endl;
    int res;
    cin >> res;
    return res;
}

 
  
int add(int x, int y, int mod = MOD)
{
    return ((x + y) % mod + mod) % mod;
}

int mul(int x, int y, int mod = MOD)
{
    return (x * 1ll * y) % mod;
}

int binpow(int x, int y, int mod = MOD)
{
    int z = add(1, 0, mod);
    while(y > 0)
    {
        if(y % 2 == 1) z = mul(z, x, mod);
        y /= 2;
        x = mul(x, x, mod);
    }
    return z;
}
ll dijkstras(vector<pair<int,int>> adj[],int S,int V)
{
 priority_queue <pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
     pq.push({0,S});
     vector<int> dis(V,1e9);
  dis[S]=0;
     while(!pq.empty())
     {
         int x=pq.top().first;
         int y=pq.top().second;
         pq.pop();
         for(auto &it:adj[y])
         {
             if(x+it.second<dis[it.first])
             {
                 dis[it.first]=x+it.second;
                 pq.push({dis[it.first],it.first});
             }
         }
     }
    ll ans=0;
    f(i,V)
    {
        if(dis[i]!=1e9)
    ans+=dis[i];
}
    return ans;

 }

void solve(int t1)
{
    ll n;
    cin>>n;
ll ar[n];
f(i,n)
cin>>ar[i];
vector<ll> dp(n+1,0);
dp[0]=1;
for(int i=0;i<n;i++)
{
vector<ll> fact;
for(int j=1;j*j<=ar[i];j++)
{
    if(ar[i]%j==0)
    {
        fact.pb(j);
        if(j*j!=ar[i])
            fact.pb(ar[i]/j);
    }
}
    rsor(fact);
    for(auto x:fact)
        {
            if(x<=n)
                dp[x]=(dp[x]+dp[x-1])%mod;
        }
}
ll ans=0;
for(int i=1;i<=n;i++)
ans=(ans+dp[i])%mod;
cout<<ans<<endl;    
}
int main()
{
   fast      
      int t=1;
      // cin>>t;
      for(int t1=1;t1<=t;t1++)
    {
        //body of the loop
   solve(t1);  
  
    }
}