Hello everyone , Please help me out by commenting your approaches/solutions of this problem which was asked in Hackwithinfy contest yesterday.Any Discussion will be appreciated .

Problem 1 :

You are given a number N .You have to find the total number of positive integer pair (A,B) such that following conditions satisfies:

1. A,B <= N
2. A^B <= X
3. A+B is divisible by D

Since the total number of pairs can be large return the answer modulo 10^9+7.

NOTE : X , D was not given in problem statement it was just given in the conditions.

Input Format

N X D

Constraints :

1 <= N <= 10^9

1 <= X <= 10^9

1 <= D <= 10^4

Sample Input

4 3 2

Sample Output

6

Explanation There are 6 pairs {(1,1),(1,3),(2,2),3,1),(3,3),(4,4)} which satisfy the condition .

test case for debugging : 100 121 2 answer will be 4778 .