洋灰是一种建筑材料，常用来筑桥搭建高层建筑，又称，水泥、混凝土。 WHZ有很多铸造成三角形的洋灰块，他想把这些洋灰三角按照一定的规律放到摆成一排的n个格子里，其中第i个格子放入的洋灰三角数量是前一个格子的k倍再多p个，特殊地，第一个格子里放1个。 WHZ想知道把这n个格子铺满需要多少洋灰三角。

输入描述:

第一行有3个正整数n，k，p。

输出描述:

输出一行，一个正整数，表示按照要求铺满n个格子需要多少洋灰三角，由于输出数据过大，你只需要输出答案模1000000007(1e9+7)后的结果即可。

备注:

对于100%的测试数据：1 ≤ n ≤ 10000000001 ≤ k,p ≤ 1000