小Z顺利通过了测量，进入了X省。为了知道现在疫情情况如何、病毒的传播速度如何，他设计了如下简化模型：
刚开始，只有一个人患病了。现在有三个整数n，k，d，分别有如下含义：
1. n：表示共进行了n轮传染。
2. k：传播指数。表示一位携带病毒的患者会把病毒传播给额外k-1个人，但自己不会痊愈。
3. d：衰减阈值。如果这次传播过后携带病毒的患者数目大于等于了d，那么携带病毒的患者数目就会除以2并下取整（在程序中，除以2下取整就是x=x/2;其中x是一个int变量）。
现在小Z告诉了你n，k，d，请你告诉他n轮传播过后，携带病毒的患者的人数是多少。
一行三个整数n,k,d，用空格隔开。
一行一个整数，表示答案。
【样例1输入】
3 2 123456
【样例2输入】
3 3 9
【样例1输出】
8
【样例2输出】
6
【样例1解释】
第一次传播后，1*2=2，小于d，数目不会减少。
第二次传播后，2*2=4，小于d，数目不会减少。
第三次传播后，4*2=8，小于d，数目不会减少。
因此答案为8。
【样例2解释】
第一次传播后，1*3=3，小于d，数目不会减少。
第二次传播后，3*3=9，大于等于d，数目除以2,9/2=4.5下取整=4。
第三次传播后，4*3=12，大于等于d，数目除以2,12/2=6下取整=6。
因此答案为6。
【数据范围】
对于40%的数据，d=2147483647。
对于另外40%的数据，k=2。
对于100%的数据，最后的答案不会超过1,000,000,000。k的n次方、d均小于等于2147483647。