SUM OR

You are given a positive integer $N$. Find the number of triples $(X, Y, Z)$ such that: - $0\lt X, Y, Z \lt N$; - $X+Y+Z=N$; - $X$ $|$ $Y$ $|$ $Z=N,$ where $|$ represents the [bitwise OR operation](https://en.wikipedia.org/wiki/Bitwise_operation#OR). Since the number of triples can be huge, print them modulo $10^9+7$. ### Input - The first line of input will contain a single integer $T$, denot