People often consider the number as lucky. “But why?” - you might ask. Well, consider the fact that if we convert the number into base-2, we get . Again, if we convert it to base-6, we get . That means, on at least two bases (), the number can be represented only using .
Now you must be thinking - “Then why stop at ? Why not other numbers as well?” To that, I say, “Sure! Why not?”.
If a positive integer can be represented only using in at least two bases (), we will call it lucky. In this problem, your task is to find the sum of all the lucky numbers less than .
The input consists of a single integer . is in base-10.
Print a single integer denoting the sum. As the answer can be large, print the answer modulo .
There are two numbers below 8 that are lucky: . So the result is .