小码君最近想到一种奇特的构造列表的方法(列表下标从 1 开始)。最初,小码君有一个列表里面只有一个数 n,然后小码君会进行 m 次操作,对于第 i 次操作:
如果 i 是奇数,小码君会将最后一个加入列表的数 ∗2,然后放入列表
如果 i 是偶数,小码君会将最后一个加入列表的数 ∗3,然后放入列表
现在小码君想要知道列表中的第 id 个数是多少。
输入格式
一行三个整数 n(1≤n≤1e9),m(1≤m≤20),id(1≤id≤m+1),表示列表中第一次加入的数、 m 次操作以及所求的数的编号。
输出格式
输出列表中第 id 个数的值。
样例组
输入#1
1 2 3
输出#1
6
提示说明
样例解释:
初始,列表中只有一个元素:{1},2次操作,我们要求列表中的第 3 个数。
第 1 次操作,最后一个数乘以 2 ,放入列表:{1,2}。
第 2 次操作,最后一个数乘以 3 ,放入列表:{1,2,6}。
列表中的第 3 个数为:6