C - たくさんの数式 / Many Formulas

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 300

問題文

1 以上 9 以下の数字のみからなる文字列 S が与えられます。 この文字列の中で、あなたはこれら文字と文字の間のうち、いくつかの場所に + を入れることができます。 一つも入れなくてもかまいません。 ただし、+ が連続してはいけません。

このようにして出来る全ての文字列を数式とみなし、和を計算することができます。

ありうる全ての数式の値を計算し、その合計を出力してください。

制約

  • 1 \leq |S| \leq 10
  • S に含まれる文字は全て 19 の数字

入力

入力は以下の形式で標準入力から与えられる。

S

出力

ありうる全ての数式の値の総和を 1 行に出力せよ。


入力例 1

125

出力例 1

176

考えられる数式としては、 1251+2512+51+2+54 通りがあります。それぞれの数式を計算すると、

  • 125
  • 1+25=26
  • 12+5=17
  • 1+2+5=8

となり、これらの総和は 125+26+17+8=176 となります。


入力例 2

9999999999

出力例 2

12656242944

Score : 300 points

Problem 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.

Constraints

  • 1 \leq |S| \leq 10
  • All letters in S are digits between 1 and 9, inclusive.

Input

The input is given from Standard Input in the following format:

S

Output

Print the sum of the evaluated value over all possible formulas.


Sample Input 1

125

Sample Output 1

176

There are 4 formulas that can be obtained: 125, 1+25, 12+5 and 1+2+5. When each formula is evaluated,

  • 125
  • 1+25=26
  • 12+5=17
  • 1+2+5=8

Thus, the sum is 125+26+17+8=176.


Sample Input 2

9999999999

Sample Output 2

12656242944