1.1 GCD / LCM#

GCD (Euclidean):

long long gcd(long long a, long long b) {
    while (b) { long long t = b; b = a % b; a = t; }
    return a;
}

LCM: lcm(a,b) = a / gcd(a,b) * b (hati-hati overflow)

1.2 Extended Euclid (modular inverse for non-prime mod)#

long long extgcd(long long a, long long b, long long &x, long long &y) {
    if (b==0) { x=1; y=0; return a; }
    long long x1,y1;
    long long g = extgcd(b, a%b, x1, y1);
    x = y1;
    y = x1 - (a/b) * y1;
    return g;
}
// inverse exists if gcd(a,mod)=1

1.3 Fast exponentiation (mod)#

long long modpow(long long a, long long e, long long mod) {
    long long r=1; a%=mod;
    while (e) {
        if (e&1) r = (__int128)r*a%mod;
        a = (__int128)a*a%mod;
        e >>= 1;
    }
    return r;
}

1.4 Modular inverse (prime mod)#

• If mod is prime: inv(a) = a^{mod-2} mod mod (use modpow).
• If not prime: use extended gcd.

1.5 Primes & Sieve of Eratosthenes (O(n log log n))#

#define ll long long
vector<ll>v;
void Sieve(ll n) {
	vector<bool> prima(n + 1, true);
	prima[1] = prima[0] = false;
	for (ll j = 4; j <= n; j += 2) {
		prima[j] = false;
	}
	for (ll i = 3; i * i <= n; i += 2) {
		if (prima[i] == true) {
			for (ll j = i * i; j <= n; j += i) {
				prima[j] = false;
			}
		}
	}
	int count{1};
	v.push_back(2 - 1);

	for (ll i = 3; i <= n; i++) {
		if (prima[i] == true) {
			ll temp = (i - (count + 2));
			v.push_back(temp);
			count += 2;
		}
	}

}

1.6 MODULAR ARITHMETIC#

Properties & reduction rules

(a + b) % m = ( (a % m) + (b % m) ) % m (a * b) % m = ( (a % m) * (b % m) ) % m**

For division: need multiplicative inverse modulo m.

Modular Exponentiation (fast powmod)

Hitung a^e mod m efisien dengan binary exponentiation (O(log e)). Sangat penting untuk crypto & CP

long long modmul(long long a, long long b, long long mod){
    return (__int128)a*b % mod;
}
long long modpow(long long a, long long e, long long mod){
    long long r = 1 % mod;
    a %= mod;
    while (e){
        if (e & 1) r = modmul(r, a, mod);
        a = modmul(a, a, mod);
        e >>= 1;
    }
    return r;
}
> Use-cases: fast power under mod, Fermat/Euler-based reductions, repeated exponent problems.

Modular inverse

If gcd(a,m) != 1 inverse mungkin tidak ada. If m prime: inv(a) = a^{m-2} mod m (Fermat). General: use Extended Euclidean Algorithm.

long long extgcd(long long a, long long b, long long &x, long long &y){
    if (b==0){ x=1; y=0; return a; }
    long long x1,y1; long long g = extgcd(b, a%b, x1, y1);
    x = y1;
    y = x1 - (a/b) * y1;
    return g;
}
long long modinv(long long a, long long m){
    long long x,y; long long g = extgcd(a,m,x,y);
    if (g != 1) return -1; // no inverse
    x %= m; if (x<0) x+=m;
    return x;
}

Exponent reduction (Euler / phi trick) If gcd(a,m)=1, Euler’s theorem: a^{φ(m)} ≡ 1 (mod m). Jadi a^e mod m = a^{ e mod φ(m) } mod m (with care when e >= φ(m) — if exponent itself large, reduce w/ φ and add φ when needed). See Totient section. Wikipedia

Warning: When gcd(a,m) != 1, reduction e mod φ(m) is NOT valid. Use CRT or handle separately.

1.7 EULER’S TOTIENT#

Definition φ(n) = count of integers 1..n that are coprime with n. (Euler’s totient / phi).

Wikipedia

Product / formula

If n = ∏ p_i^{k_i}, then
φ(n) = n * ∏_{p | n} (1 - 1/p)
     = ∏ p_i^{k_i-1} * (p_i - 1)

Compute φ(n)

By factorization: factor n, apply product formula (fast if factors known). For all i ≤ N compute φ via sieve-like method (linear or O(n log log n)):

vector<int> phi_sieve(int n){
  vector<int> phi(n+1);
  for (int i=0;i<=n;i++) phi[i]=i;
  for (int p=2;p<=n;p++) if (phi[p]==p){
    for (int k=p;k<=n;k+=p) phi[k] -= phi[k]/p;
  }
  return phi;
}

Uses

• Euler theorem (a^{φ(n)} ≡ 1 mod n if gcd(a,n)=1).
• Reduce exponents, multiplicative order, compute primitive roots (if exist).

1.8 COMBINATORICS & SPECIAL SEQUENCES#

• Permutations, combinations, Catalan numbers (handshake problem is Catalan-related — lihat link GfG).
• Quick tip: many “non-crossing” handshake arrangements = Catalan numbers.

Factorial & nCr mod (prime)

Precompute fact[] and invfact[]:

vector<long long> fact(N+1), invfact(N+1);
fact[0]=1;
for (int i=1;i<=N;i++) fact[i]=fact[i-1]*i%MOD;
invfact[N]=modpow(fact[N], MOD-2, MOD); // MOD prime
for (int i=N;i>0;i--) invfact[i-1]=invfact[i]*i%MOD;
long long nCr(int n,int r){
  if (r<0||r>n) return 0;
  return fact[n]*invfact[r]%MOD*invfact[n-r]%MOD;
}

Use Lucas theorem for very large n with prime MOD.

Catalan numbers (handshake non-crossing) Number of non-crossing handshake pairings for 2n people = C_n (Catalan). Recurrence: C_0 = 1, C_{n+1} = Σ_{i=0..n} C_i * C_{n-i}. AlgoMonster

Closed form: C_n = (1/(n+1)) * binom(2n, n).

Fibonacci (fast doubling)

Fast doubling computes F(n) mod m in O(log n).

pair<long long,long long> fib_pair(long long n, long long mod){
  if (n==0) return {0,1};
  auto p = fib_pair(n>>1, mod);
  long long a = p.first, b = p.second;
  long long c = ( (__int128)a * ( (2*b%mod - a + mod) % mod ) ) % mod;
  long long d = ( (__int128)a*a + (__int128)b*b ) % mod;
  if (n%2==0) return {c,d};
  else return {d,(c+d)%mod};
}

Short Tips / Pitfalls

• When reducing exponent using φ: only safe if gcd(base, mod) == 1. Otherwise handle separately or use CRT.
• Always watch overflow: use __int128 on products before %.
• Precompute primes & φ up to N for many queries.
• For modular inverse on composite modulus: inverse may not exist.
• For counting non-crossing structures (like handshake), map to Catalan.

Referensi singkat (untuk baca lebih lanjut)

• Euler’s totient (phi) — definition & product formula. Wikipedia
• Modular exponentiation — algorithm & notes. Wikipedia

• Catalan / Handshakes (non-crossing) — combinatorial derivation. AlgoMonster

• Chinese Remainder Theorem — theory & algorithm. Wikipedia

1.9 Factorials & nCr (with mod)#

• Precompute fact[] and invfact[] (using mod inverse) for fast nCk queries.
• Use Lucas theorem for large n with prime mod (advanced).

1.9 Factorials & nCr (with mod)#

Goal: hitung C(n, r) mod M (binomial coefficient modulo M) secara efisien untuk berbagai kasus:

• banyak query dengan n ≤ N (precompute factorial)
• n besar tapi M kecil prime (Lucas theorem)
• catatan untuk M bukan prime (kompleksitas lebih tinggi — overview)

Subset enumeration (bitmask):#

for (int mask=0; mask < (1<<n); ++mask) {
    // process subset represented by mask
}

4.1 Knapsack#

0/1 Knapsack (DP by weight):
// n items, capacity W
vector<int> dp(W+1, 0);
for (int i=0;i<n;i++){
  for (int w=W; w>=wt[i]; --w)
    dp[w] = max(dp[w], dp[w-wt[i]] + val[i]);
}

Unbounded Knapsack:
for (int i=0;i<n;i++)
  for (int w=wt[i]; w<=W; ++w)
    dp[w] = max(dp[w], dp[w-wt[i]] + val[i]);

Notes: Choose state carefully (by weight, by value, or by items). Track reconstruction if needed.

4.2 DP tips#

• Identify state and transition clearly.
• Try to reduce dimensions (rolling arrays).
• Use -INF for impossible states.
• For optimization: monotone queues, convex hull trick (advanced).

7.1 BFS (Breadth-First Search)#

• When : shortest path di graph unweighted, connectivity, level-order, shortest
• transformation (word ladder), multi-source BFS.
• Problem (contoh): Diberi graph tak-berbobot dan source s, cari jarak minimal ke semua node. Idea: queue, dist[], O(V+E).

// BFS for unweighted shortest paths
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int INF = 1e9;
vector<int> bfs(int src, const vector<vector<int>>& adj){
    int n = adj.size();
    vector<int> dist(n, INF);
    queue<int> q;
    dist[src] = 0; q.push(src);
    while(!q.empty()){
        int u = q.front(); q.pop();
        for(int v: adj[u]) if (dist[v] == INF){
            dist[v] = dist[u] + 1;
            q.push(v);
        }
    }
    return dist;
}

7.2 Dijkstra (non-negative weights)#

• When: shortest path di graph dengan bobot ≥ 0.
• Problem: shortest path dari s ke semua node (weighted).
• Idea: priority_queue (min-heap), relax edges, O((V+E) log V).

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = (1LL<<60);
vector<ll> dijkstra(int src, const vector<vector<pair<int,ll>>>& adj){
    int n = adj.size();
    vector<ll> dist(n, INF);
    priority_queue<pair<ll,int>, vector<pair<ll,int>>, greater<>> pq;
    dist[src]=0; pq.push({0,src});
    while(!pq.empty()){
        auto [d,u] = pq.top(); pq.pop();
        if (d != dist[u]) continue;
        for (auto [v,w] : adj[u]){
            if (dist[v] > d + w){
                dist[v] = d + w;
                pq.push({dist[v], v});
            }
        }
    }
    return dist;
}

7.3 Bellman–Ford (neg. weights, detect negative cycles)#

When: edge weight bisa negatif, perlu deteksi negative cycle (single-source). Problem: shortest path dengan bobot negatif. Idea: relax semua edge V-1 kali; cek relaksasi ke-V untuk negative cycle. O(V·E).

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = (1LL<<60);
struct Edge { int u,v; ll w; };
pair<vector<ll>, bool> bellman_ford(int n, int src, const vector<Edge>& edges){
    vector<ll> dist(n, INF); dist[src]=0;
    for(int i=0;i<n-1;i++){
        for(auto &e: edges){
            if (dist[e.u] != INF && dist[e.v] > dist[e.u] + e.w)
                dist[e.v] = dist[e.u] + e.w;
        }
    }
    bool negcycle = false;
    for(auto &e: edges){
        if (dist[e.u] != INF && dist[e.v] > dist[e.u] + e.w) { negcycle = true; break; }
    }
    return {dist, negcycle};
}

7.4 Kruskal (MST) + DSU#

When: cari MST di graph tak-berbobot/berbobot (undirected). Problem: minimum spanning tree total weight. Idea: urutkan edges by weight, unite jika beda komponen (DSU). O(E log E).

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct DSU {
    vector<int> p, r;
    DSU(int n): p(n), r(n,0){ iota(p.begin(), p.end(), 0); }
    int find(int x){ return p[x]==x?x:p[x]=find(p[x]); }
    bool unite(int a,int b){
        a=find(a); b=find(b);
        if (a==b) return false;
        if (r[a]<r[b]) swap(a,b);
        p[b]=a; if (r[a]==r[b]) r[a]++; return true;
    }
};
ll kruskal(int n, vector<tuple<ll,int,int>>& edges){
    sort(edges.begin(), edges.end());
    DSU dsu(n); ll cost=0;
    for(auto &t : edges){
        ll w; int u,v; tie(w,u,v)=t;
        if (dsu.unite(u,v)) cost += w;
    }
    return cost;
}

7.5 Prim (MST) — adjacency list#

When: sering berguna bila graph besar dan E ~ V^2, atau ingin implementasi langsung dari node. Idea: greedy pick min edge crossing current tree, priority_queue. O(E log V).

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll prim(int src, const vector<vector<pair<int,ll>>>& adj){
    int n = adj.size();
    vector<char> used(n,false);
    priority_queue<pair<ll,int>, vector<pair<ll,int>>, greater<>> pq;
    pq.push({0,src});
    ll total=0;
    while(!pq.empty()){
        auto [w,u]=pq.top(); pq.pop();
        if (used[u]) continue;
        used[u]=1; total += w;
        for(auto [v,wt] : adj[u]) if (!used[v]) pq.push({wt,v});
    }
    return total;
}

7.6 Topological Sort & DP on DAG#

When: DAG problems: task ordering, DP longest path on DAG, counting paths. Problem: hitung panjang jalur terpanjang di DAG. Idea: topo sort (Kahn) → relax outgoing edges in topo order → O(V+E).

(topo + longest path):

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
vector<int> topo_kahn(const vector<vector<int>>& adj){
    int n = adj.size();
    vector<int> indeg(n,0), res;
    for(int u=0;u<n;u++) for(int v: adj[u]) indeg[v]++;
    queue<int> q;
    for(int i=0;i<n;i++) if (indeg[i]==0) q.push(i);
    while(!q.empty()){
        int u=q.front(); q.pop(); res.push_back(u);
        for(int v: adj[u]) if (--indeg[v]==0) q.push(v);
    }
    return res; // if size < n => cycle exists
}
vector<ll> longest_on_dag(const vector<vector<pair<int,ll>>>& adj, int src){
    int n = adj.size();
    auto topo = topo_kahn(vector<vector<int>>(n)); // build simple adj for indeg? assume we have topo
    // In practice build topo from original adj (unweighted) or convert.
    // Here just pattern - implement according to input.
    vector<ll> dp(n, LLONG_MIN/4);
    dp[src]=0;
    for(int u: topo) if (dp[u] > LLONG_MIN/4){
        for(auto [v,w] : adj[u]) dp[v] = max(dp[v], dp[u] + w);
    }
    return dp;
}

(Note: sesuaikan pembuatan topo jika adj berisi pair; konsep tetap sama.)

7.7 SCC (Kosaraju / Tarjan)#

When: directed graph, perlu komponen kuat terhubung (2-SAT, condensation graph). Problem: hitung SCC dan buat DAG komponen. Idea (Kosaraju): DFS order → reverse graph → DFS in reverse order. Tarjan lebih ringkas (1 pass).

Kosaraju Code:

#include <bits/stdc++.h>
using namespace std;
void kosaraju(int n, const vector<vector<int>>& adj, vector<int>& comp){
    vector<int> order; vector<char> vis(n,false);
    function<void(int)> dfs1 = [&](int u){
        vis[u]=1;
        for(int v: adj[u]) if(!vis[v]) dfs1(v);
        order.push_back(u);
    };
    for(int i=0;i<n;i++) if(!vis[i]) dfs1(i);
    vector<vector<int>> radj(n);
    for(int u=0;u<n;u++) for(int v: adj[u]) radj[v].push_back(u);
    comp.assign(n, -1);
    function<void(int,int)> dfs2 = [&](int u,int cid){
        comp[u]=cid;
        for(int v: radj[u]) if(comp[v]==-1) dfs2(v,cid);
    };
    int cid=0;
    for(int i=n-1;i>=0;i--){
        int u = order[i];
        if (comp[u]==-1) { dfs2(u, cid++); }
    }
}

7.8 Bridges & Articulation Points (Tarjan cut-edge / cut-vertex)#

When: cari edges/vertices yang jika dihapus meningkatkan jumlah komponen (kritikal roads). Problem: listing all bridges. Idea: DFS track tin[u] dan low[u]. Bridge u-v jika low[v] > tin[u].

(bridges):

#include <bits/stdc++.h>
using namespace std;
int timer;
vector<int> tin, low;
vector<pair<int,int>> bridges;
void dfs_bridge(int u, int p, const vector<vector<int>>& adj){
    tin[u]=low[u]=++timer;
    for(int v: adj[u]){
        if (v==p) continue;
        if (tin[v]) { low[u] = min(low[u], tin[v]); }
        else {
            dfs_bridge(v, u, adj);
            low[u] = min(low[u], low[v]);
            if (low[v] > tin[u]) bridges.push_back({u,v});
        }
    }
}
void find_bridges(const vector<vector<int>>& adj){
    int n = adj.size();
    timer = 0; tin.assign(n,0); low.assign(n,0); bridges.clear();
    for(int i=0;i<n;i++) if(!tin[i]) dfs_bridge(i,-1,adj);
}

7.9 Lowest Common Ancestor (LCA) — Binary Lifting#

When: frequent queries LCA/kth ancestor/distance on tree. Problem: berapa LCA(u,v)? hitung jarak. Idea: preprocess up[k][v], depth[], jump. O(N log N) preprocess, O(log N) query.

#include <bits/stdc++.h>
using namespace std;
int LOG;
vector<vector<int>> up;
vector<int> depth;
void dfs_lca(int u, int p, const vector<vector<int>>& adj){
    up[0][u] = (p<0?u:p);
    for (int k=1;k<LOG;k++) up[k][u] = up[k-1][ up[k-1][u] ];
    for (int v: adj[u]) if (v!=p){
        depth[v] = depth[u] + 1;
        dfs_lca(v, u, adj);
    }
}
int lca(int a, int b){
    if (depth[a] < depth[b]) swap(a,b);
    int diff = depth[a] - depth[b];
    for (int k=0; k<LOG; ++k) if (diff & (1<<k)) a = up[k][a];
    if (a==b) return a;
    for (int k=LOG-1;k>=0;k--) if (up[k][a] != up[k][b]) { a = up[k][a]; b = up[k][b]; }
    return up[0][a];
}

7.10 Max Flow — Dinic (practical)#

When: problems modelled as flow: circulation, bipartite matching, disjoint paths, max flow min cut. Problem (contoh): bipartite matching → convert to flow, run Dinic. Idea: level graph (BFS), blocking flow (DFS), repeated.

(Dinic):

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct Dinic {
  struct Edge { int to; ll cap; int rev; };
  int n; vector<vector<Edge>> g; vector<int> level, it;
  Dinic(int n): n(n), g(n), level(n), it(n) {}
  void add_edge(int u,int v,ll c){
    g[u].push_back({v,c,(int)g[v].size()});
    g[v].push_back({u,0,(int)g[u].size()-1});
  }
  bool bfs(int s,int t){
    fill(level.begin(), level.end(), -1);
    queue<int> q; q.push(s); level[s]=0;
    while(!q.empty()){
      int u=q.front(); q.pop();
      for(auto &e: g[u]) if (e.cap>0 && level[e.to]==-1){
        level[e.to] = level[u]+1; q.push(e.to);
      }
    }
    return level[t] != -1;
  }
  ll dfs(int u,int t,ll f){
    if (!f) return 0;
    if (u==t) return f;
    for (int &i = it[u]; i < (int)g[u].size(); ++i){
      Edge &e = g[u][i];
      if (e.cap>0 && level[e.to] == level[u] + 1){
        ll ret = dfs(e.to, t, min(f, e.cap));
        if (ret){
          e.cap -= ret; g[e.to][e.rev].cap += ret;
          return ret;
        }
      }
    }
    return 0;
  }
  ll maxflow(int s,int t){
    ll flow = 0;
    while(bfs(s,t)){
      fill(it.begin(), it.end(), 0);
      while (ll f = dfs(s,t, LLONG_MAX)) flow += f;
    }
    return flow;
  }
};

Contoh penggunaan (bipartite matching): buat source → kiri nodes cap 1 → edges → kanan nodes cap1 → sink; maxflow = matching size.

7.11 Hopcroft–Karp (bipartite matching specialized)#

When: maximum bipartite matching faster in practice: O(√V · E). Problem: matching on big bipartite graphs. Idea: BFS levels + DFS augmenting.

(Karena panjang, gunakan template tim; kalau mau aku tambahkan full code Hopcroft-Karp.)

7.12 Tree DP — contoh: diameter, subtree sums#

When: penyelesaian masalah pada tree (dp per node): subtree aggregations, rerooting. Problem (contoh): tree diameter (longest path). Idea (diameter): dua BFS/DFS: pick any node → furthest a → from a furthest b → distance(a,b) = diameter.

Code (diameter):

pair<int,int> farthest(int src, const vector<vector<pair<int,int>>>& adj){
    int n = adj.size();
    vector<int> dist(n, -1);
    queue<int> q;
    q.push(src); dist[src]=0;
    while(!q.empty()){
        int u=q.front(); q.pop();
        for(auto [v,w]: adj[u]) if (dist[v]==-1){
            dist[v] = dist[u] + w; q.push(v);
        }
    }
    int best = 0, node = src;
    for(int i=0;i<n;i++) if (dist[i] > best) best = dist[i], node = i;
    return {node, best};
}
// diameter:
int tree_diameter(const vector<vector<pair<int,int>>>& adj){
    auto p = farthest(0, adj);
    auto q = farthest(p.first, adj);
    return q.second;
}

7.13 Common patterns & mapping problem→algorithm#

• If unweighted shortest path → BFS.
• If non-neg weights → Dijkstra.
• If neg weights allowed → Bellman-Ford (or Johnson if all-pairs).
• If MST → Kruskal/Prim.
• If maximum flow / matching → Dinic / Hopcroft-Karp.
• If SCC / 2-SAT → Kosaraju/Tarjan.
• If bridges/articulation → Tarjan low/tin.
• If LCA / tree queries → binary lifting + Euler tour + segtree.
• If DAG dp → topo sort → DP.

99.1. Jumlah dari Jumlah (Take/NoTake [Recursive]):#

Terdapat sebuah bilangan bulat positif S dan operator  + . Anda dapat membuat bilangan baru X yang merupakan hasil dari menempatkan nol atau lebih operator  +  di tengah dua digit bilangan S. Berikan jumlah dari seluruh kemungkinan bilangan X.

Input Baris pertama berisi bilangan bulat S (1 ≤ |S| ≤ 9).

Output Jumlah dari seluruh kemungkinan bilangan X.

Examples

Input:
1312

Output:
1856

Input:
1234567

Output:
1757440

Note Untuk test case pertama, berikut merupakan setiap kemungkinan dari X.

• 1312
• 1 + 312 = 313
• 13 + 12 = 25
• 131 + 2 = 133
• 1 + 3 + 12 = 16
• 1 + 31 + 2 = 34
• 13 + 1 + 2 = 16
• 1 + 3 + 1 + 2 = 7

Sehingga

jumlah dari seluruh X adalah: 1312 + 313 + 25 + 133 + 16 + 34 + 16 + 7 = 1856.

IPLEMENTASI 1

#include <bits/stdc++.h>
using namespace std;

#define int long long
int eval_and_print(const string &s) {
    int n = s.size();
    int m = 1 << (n-1); // setiap bit i => ada + setelah posisi i (0-based)
    int total = 0;
    for (int mask = 0; mask < m; ++mask) {
        long long cur = 0, sum = 0;
        string expr;
        for (int i = 0; i < n; ++i) {
            cur = cur*10 + (s[i]-'0');
            expr.push_back(s[i]);
            if (i < n-1 && (mask & (1<<i))) {
                // add "+" setelah i
                sum += cur;
                cur = 0;
                expr.push_back('+');
            }
        }
        sum += cur;
        cout << expr << " = " << sum << "\n";
        total += sum;
    }
    cout << "TOTAL = " << total << "\n";
    return total;
}

signed main(){
    string s;
    if (!(cin >> s)) return 0;
    eval_and_print(s);
    return 0;
}

IPLEMENTASI 2

#include <bits/stdc++.h>
using namespace std;
#define ll long long

struct DATA {
	int l, x, r;
};

// Function to find all substrings
vector<DATA> findSubstrings(string &s) {

	// to store all substrings
	vector<DATA> res;
	vector<DATA>v;
	for (int i = 0; i < s.length(); i++) {
		for (int j = i; j < s.length(); j++) {http://localhost:4321/posts/cheatsheet_cp/#3-greedy

			// substr function takes starting index
			// and length as parameters
			res.push_back({i, stoi(s.substr(i, j - i + 1)), (s.size() - (j + 1))});

////			cout << i << " " << res[j] << " " << s.size() - (j + 1) << '\n';
//			v.push_back({i, stoi(res[j]), (s.size() - (j + 1))});
		}
	}

	return res;
}

int main() {
	string s;
	ll sum{0};
	cin >> s;
	int dp[30];
	dp[0] = 1;
	dp[1] = 1;
	for (int i = 2; i < 30; i++) {
		dp[i] = dp[i - 1] * 2;
	}
	vector<DATA> res = findSubstrings(s);
	for (auto i : res) {
//		cout << i.l << " " << i.x << " " << i.r << '\n';
		//1=1
		//2=2
		//3=4
		//4=8
		sum += (dp[i.l] * dp[i.r] * i.x);
	}
	cout << sum << '\n';
	return 0;
}
/*

REFF:
https://www.geeksforgeeks.org/dsa/program-print-substrings-given-string/

*/