stablegradients/pie-gem5-pairs huggingface dataset:
// Slower C++ solution:
#include <bits/stdc++.h>

using namespace std;

using ll = long long;

using ld = long double;

using vl = vector<ll>;

using vll = vector<vl>;

using Pll = pair<ll, ll>;

#define rep(i,n) for(ll i=0;i<(ll)(n);i++)

#define all(v) v.begin(), v.end()

#define sz(x) ((int) x.size())

#define pb push_back

#define mp make_pair

#define mt make_tuple

#define F first

#define S second

const int MOD = 1e9+7;

const ll INF = 2e18;

template<class T> void print(const T& t){ cout << t << endl; }

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }

template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

int gcd(int a,int b){return b?gcd(b,a%b):a;}



int main(){

  ll n;

  cin >> n;

  vl a(n);

  vector<bool> z(1000007, true);

  vector<bool> z1(1000007, false);

  rep(i, n){

    cin >> a[i];

    if(z[a[i]]){

      for (ll j = 2; a[i] * j < 1000007; j++){

        z[a[i] * j] = false;

      }

      if(z1[a[i]])z[a[i]] = false;

      z1[a[i]] = true;

    }

  }

  ll ans = 0;

  rep(i, n){

    if(z[a[i]])

      ans++;

  }

  print(ans);

}


// Faster C++ solution for the same problem (measured speedup: 2.559627587956421x):
#include <bits/stdc++.h>

using namespace std;

int exist[1000005];

int max1;

int min1=0x3f3f3f3f;

int end1;

bool flag[1000005];

void sieve()

{

    for(int i=min1;i<=max1;i++)

    {

    	if(exist[i]==1)

        {

            for(int j=2*i;j<=max1;j+=i)

            {

                if(exist[j]&&flag[j]==0)

                {

                    exist[j]--;

                    end1--;

                }

            }

        }

    }

}

int x;

int main() 

{

    int n;cin>>n;

	for(int i=1;i<=n;i++)

    {

        cin>>x;

        exist[x]++;

        max1=max(max1,x);

        min1=min(min1,x);

    }

    for(int i=min1;i<=max1;i++)

    {

    	if(exist[i]==1)

    	{

    		end1++;

		}

		else if(exist[i]>1)

		{

			exist[i]=1;

			flag[i]=1;

		}

	}

    sieve();

    cout<<end1;

}
// Slower C++ solution:
#include<iostream>

#include<iomanip>

#include<cmath>

#include<string>

#include<vector>

#include<list>

#include<algorithm>

#include<map>

#include<set>

#include<queue>

#include<stack>

using namespace std;

typedef long long ll;

#define fi first

#define se second

#define mp make_pair

#define rep(i, n) for(int i=0;i<n;++i)

#define rrep(i, n) for(int i=n;i>=0;--i)

const int inf=1e9+7;

const ll mod=1e9+7;

const ll big=1e18;

const double PI=2*asin(1);



int main() {

  int N;

  cin>>N;

  vector<int> A(N);

  for(int i=0;i<N;++i){

    cin>>A[i];

  }

  sort(A.begin(), A.end());

  map<int, int> amap;

  int tmpA;

  bool ok[1000005];

  for(int i=0;i<1000005;++i){

    ok[i] = false;

  }

  for(int i=0;i<N;++i){

    tmpA = A[i];

    for(int j=1;j*j<=tmpA;++j){

      if(tmpA%j==0){

        if(amap[j]>0 || amap[tmpA/j]>0) {

          ok[tmpA] = true;

        }

      }

    }

    amap[A[i]]++;

  }

  int ans = 0;

  for(int i=0;i<N;++i){

    if(ok[A[i]]==false) {

      ans++;

    }

  }

  cout<<ans<<endl;

}




// Faster C++ solution for the same problem (measured speedup: 1.9840032243379102x):
#include<iostream>

#include<iomanip>

#include<cmath>

#include<string>

#include<cstring>

#include<vector>

#include<list>

#include<algorithm>

#include<map>

#include<set>

#include<queue>

#include<stack>

using namespace std;

typedef long long ll;

#define fi first

#define se second

#define mp make_pair

#define mt make_tuple

#define pqueue priority_queue

const int inf=1e9+7;

const ll mod=1e9+7;

const ll mod1=998244353;

const ll big=1e18;

const double PI=2*asin(1);



int main() {

  int N;

  cin>>N;

  vector<int> A(N);

  for(int i=0;i<N;++i) cin>>A[i];

  sort(A.begin(), A.end());

  int ans[A[A.size()-1]+1];

  for(int i=0;i<=A[A.size()-1];++i) ans[i] = 0;

  map<int, int> amap;

  for(int i=0;i<N;++i) {

    amap[A[i]]++;

    for(int j=2;A[i]*j<=A[A.size()-1];++j) {

      ans[A[i]*j]++;

    }

  }

  int ans1 = 0;

  for(int i=0;i<=A[A.size()-1];++i) {

    if(amap[i]==1 && ans[i]==0) ans1++;

  }

  cout<<ans1<<endl;

}
// Slower C++ solution:
#include<iostream>

#include<iomanip>

#include<cmath>

#include<string>

#include<vector>

#include<list>

#include<algorithm>

#include<map>

#include<set>

#include<queue>

#include<stack>

using namespace std;

typedef long long ll;

#define fi first

#define se second

#define mp make_pair

#define rep(i, n) for(int i=0;i<n;++i)

#define rrep(i, n) for(int i=n;i>=0;--i)

const int inf=1e9+7;

const ll mod=1e9+7;

const ll big=1e18;

const double PI=2*asin(1);



int main() {

  int N;

  cin>>N;

  vector<int> A(N);

  for(int i=0;i<N;++i){

    cin>>A[i];

  }

  sort(A.begin(), A.end());

  map<int, int> amap;

  int tmpA;

  bool ok[1000005];

  for(int i=0;i<1000005;++i){

    ok[i] = false;

  }

  for(int i=0;i<N;++i){

    tmpA = A[i];

    for(int j=1;j*j<=tmpA;++j){

      if(tmpA%j==0){

        if(amap[j]>0 || amap[tmpA/j]>0) {

          ok[tmpA] = true;

        }

      }

    }

    amap[A[i]]++;

  }

  int ans = 0;

  for(int i=0;i<N;++i){

    if(ok[A[i]]==false) {

      ans++;

    }

  }

  cout<<ans<<endl;

}




// Faster C++ solution for the same problem (measured speedup: 1.9857124799046746x):
#include<iostream>

#include<iomanip>

#include<cmath>

#include<string>

#include<cstring>

#include<vector>

#include<list>

#include<algorithm>

#include<map>

#include<set>

#include<queue>

#include<stack>

using namespace std;

typedef long long ll;

#define fi first

#define se second

#define mp make_pair

#define mt make_tuple

#define pqueue priority_queue

const int inf=1e9+7;

const ll mod=1e9+7;

const ll mod1=998244353;

const ll big=1e18;

const double PI=2*asin(1);



int main() {

  int N;

  cin>>N;

  vector<int> A(N);

  for(int i=0;i<N;++i) cin>>A[i];

  sort(A.begin(), A.end());

  int ans[A[A.size()-1]+1];

  for(int i=0;i<=A[A.size()-1];++i) ans[i] = 0;

  map<int, int> amap;

  for(int i=0;i<N;++i) {

    if(ans[A[i]]>0) continue;

    amap[A[i]]++;

    for(int j=2;A[i]*j<=A[A.size()-1];++j) {

      ans[A[i]*j]++;

    }

  }

  int ans1 = 0;

  for(int i=0;i<=A[A.size()-1];++i) {

    if(amap[i]==1 && ans[i]==0) ans1++;

  }

  cout<<ans1<<endl;

}
// Slower C++ solution:
#include <bits/stdc++.h>

#include <ext/pb_ds/assoc_container.hpp>

#define pb push_back

#define mp make_pair

#define f first

#define s second

#define ll long long

#define endl "\n"

using namespace __gnu_pbds;

template <typename T> using ordered_set = tree<T, null_type, std::less<T>, rb_tree_tag, tree_order_statistics_node_update>;

using namespace std;

const int N = 1e6 + 10;

const ll inf = 1e18 + 10, mod = 1e9 + 7;

int n, m[N], a[N], ans;

int main()

{

    ios_base :: sync_with_stdio(0);cin.tie(0);cout.tie(0);

    //freopen("lca_rmq.in", "r", stdin);

    //freopen("lca_rmq.out", "w", stdout);

    cin >> n;

    for(int i = 1; i <= n; i++)

    {

        cin >> a[i];

        m[a[i]]++;

    }

    for(int i = 1; i <= n; i++)

    {

        int t = 0;

        for(int j = 2; j * j <= a[i]; j++)

        {

            if(a[i] % j == 0)

            {

                if(m[j])t = 1;

                if(j * j != a[i] && m[a[i] / j])t = 1;

            }

        }

        if(m[1] && a[i] != 1)t = 1;

        if(!t && m[a[i]] <= 1)ans++;

    }

    cout << ans;

}
































// Faster C++ solution for the same problem (measured speedup: 5.377009221477234x):
#include <stdio.h>

#define N 1000001



int c[N] = {0}, a[200002];

char f[N] = {0};



int read()

{

	char c;

	while((c = getchar()) < 48 || c > 57);

	int x = c - 48;

	while((c = getchar()) > 47 && c < 58) x = x * 10 + c - 48;

	return x;

}



int main()

{		

	int n, m = 0, i, j, ans = 0, x;

		

	n = read();

	for(i = 0; i < n; i++){

		a[i] = x = read();

		if(x > m) m = x;

		c[x]++;

	}

	for(i = 1; i <= m; i++){

		if(!c[i]) continue;

		for(j = i << 1; j <= m; j += i) f[j] = 1;

	}

	for(i = 0; i < n; i++){

		x = a[i];

		if(c[x] == 1 && !f[x]) ans++;

	}

	printf("%d\n", ans);	

			

	return 0;

}
// Slower C++ solution:
#define _USE_MATH_DEFIMES

#include <algorithm>

#include <array>

#include <bitset>

#include <cassert>

#include <cctype>

#include <climits>

#include <clocale>

#include <cmath>

#include <complex>

#include <cstdio>

#include <cstdlib>

#include <ctime>

#include <deque>

#include <fstream>

#include <functional>

#include <iomanip>

#include <iostream>

#include <iterator>

#include <list>

#include <map>

#include <numeric>

#include <queue>

#include <regex>

#include <set>

#include <sstream>

#include <stack>

#include <string>

#include <tuple>

#include <unordered_map>

#include <unordered_set>

#include <utility>

#include <vector>



const int MOD = 1'000'000'007;

const int INF = 1'000'000'000; //1e9

const int NIL = -1;

const long long LINF = 1'000'000'000'000'000'000; // 1e18

const long double EPS = 1E-10;



template<class T, class S> inline bool chmax(T &a, const S &b){

    if(a < b){

        a = b; return true;

    }

    return false;

}

template<class T, class S> inline bool chmin(T &a, const S &b){

    if(b < a){

        a = b; return true;

    }

    return false;

}















int main(){

    int N; std::cin >> N;

    std::vector<int> A(N);

    int mxa(0);

    for(int i(0); i < N; ++i){

        std::cin >> A[i];

        chmax(mxa, A[i]);

    }

    std::sort(std::begin(A), std::end(A));

    std::vector<bool> okay(mxa + 1, true), has(mxa + 1, false);

    for(int i(0); i < N; ++i){

        if(has[A[i]]) okay[A[i]] = false;

        if(okay[A[i]]){

            for(int j(2*A[i]); j <= mxa; j += A[i]){

                okay[j] = false;

            }

            has[A[i]] = true;

        }

    }

    int ans(0);

    for(int i(0); i < N; ++i) if(okay[A[i]]) ++ans;

    std::cout << ans << std::endl;

    return 0;

}


// Faster C++ solution for the same problem (measured speedup: 5.334079628366703x):
#include <stdio.h>

#define N 1000001



int c[N] = {0}, a[200002];

char f[N] = {0};



int read()

{

	char c;

	while((c = getchar()) < 48 || c > 57);

	int x = c - 48;

	while((c = getchar()) > 47 && c < 58) x = x * 10 + c - 48;

	return x;

}



int main()

{		

	int n, m = 0, i, j, ans = 0, x;

		

	n = read();

	for(i = 0; i < n; i++){

		a[i] = x = read();

		if(x > m) m = x;

		c[x]++;

	}

	for(i = 1; i <= m; i++){

		if(!c[i]) continue;

		for(j = i << 1; j <= m; j += i) f[j] = 1;

	}

	for(i = 0; i < n; i++){

		x = a[i];

		if(c[x] == 1 && !f[x]) ans++;

	}

	printf("%d\n", ans);	

			

	return 0;

}
// Slower C++ solution:
#include <iostream>

#include <vector>

#include <algorithm>



using namespace std;



int main()

{

	int n;

	cin >> n;

	vector<int> a(n);

	int c[1000100] = {};

	for (int i = 0; i < n; i++) {

		cin >> a[i];

		c[a[i]]++;

	}

	if (c[1] >= 2) {

		cout << 0 << endl;

		return 0;

	} else if (c[1] == 1) {

		cout << 1 << endl;

		return 0;

	}



	vector<vector<int>> b(n);

	for (int i = 0; i < n; i++) {

		for (int j = 2; j * j <= a[i]; j++) {

			if (a[i] % j == 0) {

				b[i].emplace_back(j);

				b[i].emplace_back(a[i] / j);

			}

		}

	}

	

	int ans = 0;

	for (int i = 0; i < n; i++) {

		if (c[a[i]] >= 2) {

			continue;

		}

		bool ok = true;

		for (auto & j : b[i]) {

			if (c[j] != 0) {

				ok = false;

				break;

			}

		}

		if (ok) {

			ans++;

		}

	}

	cout << ans << endl;



	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 0.6608245036148281x):
#include <iostream>

#include <vector>

#include <algorithm>



using namespace std;



int c[1000100] = {};

int f[1000100] = {};



int main()

{

	int n;

	cin >> n;

	vector<int> a(n);

	for (int i = 0; i < n; i++) {

		cin >> a[i];

		c[a[i]]++;

	}

	sort(a.begin(), a.end());

	a.erase(unique(a.begin(), a.end()), a.end());

	

	for (int i = 0; i < a.size(); i++) {

		for (int j = a[i]; j < 1000100; j += a[i]) {

			f[j] += c[a[i]];

		}

	}



	int ans = 0;

	for (int i = 0; i < a.size(); i++) {

		if (f[a[i]] == 1) {

			ans++;

		}

	}

	cout << ans << endl;



	return 0;

}
// Slower C++ solution:
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

#define MM 1000000000

#define MOD MM+7

#define MAX 101000

#define MAP 110

#define initial_value -1

#define Pair pair<int,int>

#define lPair pair<ll,ll>

#define chmax(a,b) (a<b ? a=b:0)

#define chmin(a,b) (a>b ? a=b:0)

int dx[4] = {-1,0,1,0};

int dy[4] = {0,-1,0,1};



vector<int> places[200200];

ll dp[200200];

void add(ll &a, ll b) { a+=b; if(a >= MOD) a -= MOD;}

int main(){

    int N; cin >> N;

    map<char,int> mp;

    string s; cin >> s;

    for(int i = 0; i < N; i++){

        mp[s[i]]++;

    }

    ll ans = 1;

    for(char t = 'a'; t <= 'z'; t++){

        if(mp[t] == 0) continue;

        ans *= (mp[t]+1);

        ans %= MOD;

    }

    cout << ans-1 << endl;

}

// Faster C++ solution for the same problem (measured speedup: 6.404255023616365x):
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

typedef long long int llint;

#define MM 1000000000

#define MOD MM+7

#define MAX 101000

#define MAP 110

#define initial_value -1

#define Pair pair<int,int>

#define chmax(a,b) (a<b ? a=b:0)

#define chmin(a,b) (a>b ? a=b:0)

#define INF (1 << 29) //536870912

int dx[4] = {-1,0,1,0};

int dy[4] = {0,-1,0,1};

int main(){

    int n; cin >> n;

    string s; cin >> s;

    map<char,int> mp;

    for(int i = 0; i < n; i++){

        mp[s[i]]++;

    }

    ll ans = 1;

    for(char t = 'a'; t <= 'z'; t++){

        if(mp[t] == 0) continue;

        ans *= (mp[t] + 1);

        ans %= MOD;

    }

    cout << ans-1 << endl;

}
// Slower C++ solution:
#include <bits/stdc++.h>

using namespace std;

const long long mod = 1e9 + 7;

map<char , int>m;

char c;

int n;

long long sum;

int main(){

	cin >> n;

	for(int i = 1 ; i <= n ; i++){

		cin >> c;

		m[c]++; 

	}

	sum = 1;

	for(char i = 'a' ; i <= 'z' ; i++){

		sum *= (m[i] + 1);

		sum %= mod;

	}

	cout << sum - 1 << endl;

}

// Faster C++ solution for the same problem (measured speedup: 5.262028696472978x):
#include<cstdio>



using namespace std;



char s[100002];

int z[26];

int main(){

	int n;

	scanf("%d%s",&n,s+1);

	for(int i=1;i<=n;i++)

		z[s[i]-'a']++;

	int ans=1;

	for(int i=0;i<26;i++)

		ans=1ll*ans*(z[i]+1)%1000000007;

	printf("%d\n",(ans-1+1000000007)%1000000007);

}
// Slower C++ solution:
#include <bits/stdc++.h>



using namespace std;



const int mod = int(1e9) + 7;



int n;

char s[100005];

int cnt[26];



int main() {

	scanf("%d%s", &n, s);

	for (int i = 0; i < n; ++i) ++cnt[s[i] - 'a'];

	int ans = 1;

	for (int i = 0; i < 26; ++i) ans = 1LL * ans * (cnt[i] + 1) % mod;

	printf("%d\n", (ans - 1 + mod) % mod);

}

// Faster C++ solution for the same problem (measured speedup: 5.166485538321226x):
#include<cstdio>



using namespace std;



char s[100002];

int z[26];

int main(){

	int n;

	scanf("%d%s",&n,s+1);

	for(int i=1;i<=n;i++)

		z[s[i]-'a']++;

	int ans=1;

	for(int i=0;i<26;i++)

		ans=1ll*ans*(z[i]+1)%1000000007;

	printf("%d\n",(ans-1+1000000007)%1000000007);

}
// Slower C++ solution:
#include<bits/stdc++.h>

#define range(i,a,b) for(int i = (a); i < (b); i++)

#define rep(i,b) for(int i = 0; i < (b); i++)

#define all(a) (a).begin(), (a).end()

#define show(x)  cerr << #x << " = " << (x) << endl;

#define int long long

using namespace std;



template <typename X, typename T>

auto vectors(X x, T a) {

	return vector<T>(x, a);

}



template <typename X, typename Y, typename Z, typename... Zs>

auto vectors(X x, Y y, Z z, Zs... zs) {

	auto cont = vectors(y, z, zs...);

	return vector<decltype(cont)>(x, cont);

}



template<typename T>

ostream& operator << (ostream& os, vector<T>& v){

	rep(i,v.size()){ os << v[i] << (i == v.size() - 1 ? "" : " "); } return os;

}

template<typename T>

istream& operator >> (istream& is, vector<T>& v){

	for(T& x: v){ is >> x; } return is;

}



const int M = 1000000007;



signed main(){

	int n;

	string s;

	cin >> n >> s;



	vector<int> num(26, 0);

	for(auto i : s){

		num[i - 'a']++;

	}



	vector<int> a, b;

	rep(s,1 << 13){

		int sum = 1;

		rep(j,13){

			if((s >> j) bitand 1){

				(sum *= num[j]) %= M;

			}

		}

		a.emplace_back(sum);

	}



	rep(s,1 << 13){

		int sum = 1;

		rep(j,13){

			if((s >> j) bitand 1){

				(sum *= num[j + 13]) %= M;

			}

		}

		b.emplace_back(sum);

	}



	int ans = 0;

	int b_sum = 0;

	rep(i,b.size()){

		(b_sum += b[i]) %= M;

	}

	rep(i,a.size()){

		(ans += a[i] * b_sum % M) %= M;

	}



	cout << ans - 1 << endl;

}


// Faster C++ solution for the same problem (measured speedup: 2.591736404894399x):
#include<bits/stdc++.h>

#define range(i,a,b) for(int i = (a); i < (b); i++)

#define rep(i,b) for(int i = 0; i < (b); i++)

#define all(a) (a).begin(), (a).end()

#define show(x)  cerr << #x << " = " << (x) << endl;

#define int long long

using namespace std;



template <typename X, typename T>

auto vectors(X x, T a) {

	return vector<T>(x, a);

}



template <typename X, typename Y, typename Z, typename... Zs>

auto vectors(X x, Y y, Z z, Zs... zs) {

	auto cont = vectors(y, z, zs...);

	return vector<decltype(cont)>(x, cont);

}



template<typename T>

ostream& operator << (ostream& os, vector<T>& v){

	rep(i,v.size()){ os << v[i] << (i == v.size() - 1 ? "" : " "); } return os;

}

template<typename T>

istream& operator >> (istream& is, vector<T>& v){

	for(T& x: v){ is >> x; } return is;

}



const int M = 1000000007;



signed main(){

	int n;

	string s;

	cin >> n >> s;



	vector<int> num(26, 0);

	for(auto i : s){

		num[i - 'a']++;

	}





	int ans = 1;

	rep(i,num.size()){

		(ans *= num[i] + 1) %= M;

	}



	cout << ans - 1 << endl;

}
// Slower C++ solution:
#include <bits/stdc++.h>



using namespace std;



typedef unsigned long long int ll;



ll inf = 1e9+7;



int main()

{

    ios::sync_with_stdio(0);

    std::cin.tie(0);

    ll n;

    char c;

    cin >> n;

    vector<ll> s(n+1,0);

    for(ll i = 1; i <= n; i++)

    {

        cin >> c;

        s.at(i) = (ll)((c-'a')+1);

    }



    sort(s.begin(), s.end());



    vector<ll> dp(1e5+1,0);

    vector<ll> b(1e5+1,0);

    ll tem, tem2;



    for(ll i = 1; i <= n; i++)

    {

        tem = s[i];

        if(b.at(tem) == 0)

        {

            dp.at(i) = (2*dp.at(i-1)+1)%inf;

        }

        else

        {

            dp.at(i) = ((2*dp.at(i-1)%inf) + inf - dp.at(b.at(tem)-1) )%inf;

        }

        b.at(tem) = i;

    }





    cout << dp.at(n);











    return 0;

}


// Faster C++ solution for the same problem (measured speedup: 2.5892043410411008x):
#include <bits/stdc++.h>



using namespace std;



typedef long long int ll;



ll inf = 1e9+7;



int main()

{

    ios::sync_with_stdio(0);

    cin.tie(0);

    int n, k, d;

    cin >> n;

    vector<int> a(26,0);



    char c;

    for(int i = 0; i < n; i++)

    {

        cin >> c;

        a.at(c-'a')++;

    }



    ll sum = 1;

    for(int i = 0; i < 26; i++)

    {

        sum *= (ll)(a.at(i)+1);

        sum %= inf;

    }



    cout << (sum-1);









    return 0;

}
// Slower C++ solution:
#include<bits/stdc++.h>

#define MAXN 100005

#define mod 1000000007

typedef long long ll;

using namespace std;

vector<ll> arr,book,dp;

int main(){

    ll n;

    cin >> n;

    arr.assign(n,0);

    book.assign(MAXN,0);

    dp.assign(MAXN,0);

    char x;

    for(ll i=0;i<n;i++){

        cin >> x;

        arr[i]=x-'a'+1;

    }

    sort(arr.begin(),arr.end());

    for(ll i=1;i<=n;i++){

        if(!book[arr[i-1]]){

            dp[i]=(2*dp[i-1]+1)%mod;

        }

        else{

            int t=book[arr[i-1]];

            dp[i]=(dp[i-1]*2%mod+mod-dp[t-1]%mod)%mod;

        }

        book[arr[i-1]]=i;

    }

    cout << dp[n]%mod << '\n';

    return 0;

}


// Faster C++ solution for the same problem (measured speedup: 2.623469506935751x):
#include <bits/stdc++.h>

#define foi for(int i=0; i<n; i++)

#define foj for(int j=0; j<n; j++)

#define ll long long int

#define vi vector<int>

#define maxn 200005

#define mod 1000000007

using namespace std;



int cnt[30];

char c;

int main() {

    int n;

    cin >> n;

    foi {

        cin >> c;

        cnt[c-'a']++;

    }

    ll ans=1;

    for (int i=0; i<30; i++) {

        ans=ans*(cnt[i]+1)%mod;

    }

    ans--;

    if (ans<0) ans+=mod;

    cout << ans << '\n';

    return 0;

}
// Slower C++ solution:
#include <bits/stdc++.h>

using namespace std;

using ll = long long;

using vi = vector<int>;

using vc = vector<char>;

using vb = vector<bool>;

using vd = vector<double>;

using vs = vector<string>;

using vll = vector<long long>;

using vpii = vector<pair<int, int>>;

using vvi = vector<vector<int>>;

using vvc = vector<vector<char>>;

using vvs = vector<vector<string>>;

using vvb = vector<vector<bool>>;

using pii = pair<int, int>;

#define rep(i,n) for(int i = 0; i < (int)(n); i++)

#define reps(i,n) for(int i = 1; i <= (int)(n); i++)

#define rrep(i,n) for(int i = (int)(n) - 1; i >= 0; i--)

#define rreps(i,n) for(int i = (int)(n); i > 0; i--)

#define FOR(i,a,b) for(int i = (int)(a); i <= (int)(b); i++)

#define RFOR(i,a,b) for(int i = (int)(a); i >= (int)(b); i--)

#define all(x) (x).begin(), (x).end()

#define rall(x) (x).rbegin(), (x).rend()

#define call(x) (x).cbegin(), (x).cend()

#define MAX(x) *max_element(all(x))

#define MIN(x) *min_element(all(x))

template<class T> inline bool chmax(T &a, T b) {if (a<b) {a=b; return 1;} return 0;}

template<class T> inline bool chmin(T &a, T b) {if (b<a) {a=b; return 1;} return 0;}

const int INF = INT_MAX;

const int MOD = 1000000007;

const int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};

const int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};



int main() {

    int N;

    cin >> N;

    vll dp(100500, INF);

    dp[0] = 0;

    reps(i, N) {

        int j = 0;

        while (i - pow(6, j) >= 0) {

            chmin(dp[i], dp[i - pow(6, j)] + 1);

            j++;

        }

        j = 0;

        while (i - pow(9, j) >= 0) {

            chmin(dp[i], dp[i - pow(9, j)] + 1);

            j++;

        }

    }

    cout << dp[N] << endl;

}

// Faster C++ solution for the same problem (measured speedup: 2.75301156011955x):
#include <bits/stdc++.h>

#define rep(i,n) for(int i = 0; i < (int)(n); i++)

#define fi first

#define se second

#define pb push_back

#define eb emplace_back

#define sz(x) (int)(x).size()

#define all(v) v.begin(), v.end()

using namespace std;

using ll = long long;

using P = pair<int, int>;

using vi = vector<int>;

using vc = vector<char>;

using vb = vector<bool>;

using vs = vector<string>;

using vll = vector<long long>;

using vp = vector<pair<int, int>>;

using vvi = vector<vector<int>>;

using vvc = vector<vector<char>>;

using vvll = vector<vector<long long>>;

template<class T> inline bool chmax(T &a, T b) { if (a<b) {a=b; return 1;} return 0;}

template<class T> inline bool chmin(T &a, T b) { if (b<a) {a=b; return 1;} return 0;}



const int INF = 1001001001;



int main() {

    ios::sync_with_stdio(false);

    cin.tie(0);



    int n;

    cin >> n;

    vector<int> dp(n+1, INF);

    dp[0] = 0;

    for (int i = 1; i <= n; ++i) {

        int power = 1;

        while (i - power >= 0) {

            chmin(dp[i], dp[i - power] + 1);

            power *= 6;

        }

        power = 1;

        while (i - power >= 0) {

            chmin(dp[i], dp[i - power] + 1);

            power *= 9;

        }

    }

    cout << dp[n] << endl;

}