output_description: Print the sum of the evaluated value over all possible formulas.
  
  * * *
input_description: The input is given from Standard Input in the following format:
  
      
      
      S
attempt: # -*- coding: utf-8 -*-
  S = input()
  
  n = len(S)
  
  sum_formula = 0
  # bit全探索
  for bit in range(2 ** (n - 1)):
      nums = []
      # 何ビットシフトさせるか
      num = S[0]
      for shift in range(n - 1):
          if not ((bit >> shift) & 1):
              num = num + S[shift + 1]
          else:
              nums.append(int(num))
              num = S[shift + 1]
      nums.append(int(num))
      sum_formula += sum(nums)
  
  print(sum_formula)
  
  
  # 再帰関数
  def calc_all_formula(S, i, lists):
      """
      listsの要素: ([数字list], temp_str)
      """
      new_lists = []
      # i - i+1番目の間に+が入る
      new_lists.extend([(lst[0] + [int(lst[1])], S[i + 1]) for lst in lists])
      new_lists.extend([(lst[0], lst[1] + S[i + 1]) for lst in lists])
  
      # base case
      if i == len(S) - 2:
          new_lists = [lst[0] + [int(lst[1])] for lst in new_lists]
          return new_lists
  
      return calc_all_formula(S, i + 1, new_lists)
  
  
  # base_cand = [([], S[0])]
  
  # if len(S) >= 2:
  #     sum_formula = sum([sum(lst) for lst in calc_all_formula(S, 0, base_cand)])
  #     print(sum_formula)
  # else:
  #     print(int(S))
  
problem_description: Statement
  
  You are given a string S consisting of digits between `1` and `9`, inclusive.
  You can insert the letter `+` into some of the positions (possibly none)
  between two letters in this string. Here, `+` must not occur consecutively
  after insertion.
  
  All strings that can be obtained in this way can be evaluated as formulas.
  
  Evaluate all possible formulas, and print the sum of the results.
samples: [{"input": "125", "output": "176\n    \n\nThere are 4 formulas that can be obtained: `125`, `1+25`, `12+5` and `1+2+5`.\nWhen each formula is evaluated,\n\n  * 125\n  * 1+25=26\n  * 12+5=17\n  * 1+2+5=8\n\nThus, the sum is 125+26+17+8=176.\n\n* * *"}, {"input": "9999999999", "output": "12656242944"}]