100522 - 数的二进制表示

Time Limit

50 毫秒

Memory Limit

128 MB

通过次数

3

提交次数

7

任何整数都可以用二进制表示,而二进制的位权为2^n(0\le n),于是任何整数都可以表示为2的幂次方相加的形式,如:

13用二进制表示为:1101,即13 = 2^3 + 2^2 + 2^0

输入一个非负整数x,输出其用2的幂次方相加表示的形式。

Input

一行,一个整数,表示x

对于100%的数据:

0 < x \le 1\cdot 10^9

Output

一行,用2的幂次方相加表示的x,其中不得含值为0的项,每个字符之间不得有多余的空格。

Examples

Input

13

Output

2^3+2^2+2^0

Hint

二进制位运算:

左移<<:将二进制左移一位(超出范围的舍弃)

右移>>:将二进制右移一位(超出范围的舍弃)

与&:进行二进制与操作——对应二进制位上均为1的结果为1,否则为0。

或|:进行二进制或操作——对应二进制位上有为1的结果为1,否则为0。

非~:进行二进制非操作——对应二进制位上的0变1,1变0。

异或^:进行二进制异或运算——对应二进制位上数字不同为1,否则为0;即0、0或1、1结果为0,0、1或1、0结果为1。将一个数连续两次异或另一个数,其值不变。

提示:位运算速度要比循环的方法快很多。