题目描述

小C最近在学习集合论，他遇到了这样一个问题：给定一个集合S，包含n个元素，每个元素有一个权值。 他想知道，对于S的每一个非空子集T，再对T的每一个非空子集U，计算U的权值和（即U中所有元素之和），然后将这些权值和相加。（即子集的子集） 但是小C不会做，所以他需要你的帮助。

输入格式

第一行一个整数n，表示集合S的大小。 第二行n个整数，表示集合S中每个元素的权值。

输出格式

输出一个整数，表示答案。

2
1 2

9

3
1 2 3

54

提示

n<=12

对于样例一，一共有四个子集

{} 一共有一个子集，答案贡献是0

{1} 一共有两个子集，答案贡献是1

{2} 一共有两个子集，答案贡献是2

{1，2} 有四个子集，答案贡献是1+2+1+2=6