It was a long time since Informikas has had something to do with recursions and this had to be fixed. For that reason he decided to come up with some recursion and later solve it all by himself.
The first recursion Informikas managed to come up was
"Nah, too easy", he told to himself, crumpled the paper and threw it to a trash can.
"Squaring is overrated. Still too easy", he thought while the paper was flying towards a trash can.
"Oh no, what have I done! This recursion has no terminating condition! It's too hard even for me!", Informikas shouted out loud.
Could you be so kind and, given the value of a, help out Informikas by finding the value of h(0).
Single integer a (0 ≤ a ≤ 1018).
Calculate the integer part of h(0). As the answer can be quite a large number, output it modulo 109 + 7 (1000000007). In cases when the recursion goes infinitely long, output "Nobody got time for that" (without quotation marks).
## Input
Single integer a (0 ≤ a ≤ 1018).
## Output
Calculate the integer part of h(0). As the answer can be quite a large number, output it modulo 109 + 7 (1000000007). In cases when the recursion goes infinitely long, output "Nobody got time for that" (without quotation marks).
[samples]
**Definitions**
Let $ T \in \mathbb{Z} $ be the number of test cases.
For each test case $ k \in \{1, \dots, T\} $:
- Let $ N_k \in \mathbb{Z} $ denote the dimension of the square matrix.
- Let $ W_k \in \mathbb{Z} $ denote the upper bound on the submatrix sum.
- Let $ A_k = (a_{i,j}^{(k)})_{i,j=1}^{N_k} $ be an $ N_k \times N_k $ matrix with positive integer entries.
For a square submatrix of size $ s \times s $ with top-left corner at $ (i,j) $, define its **diagonal sum** as:
$$
S(i,j,s) = \sum_{d=0}^{s-1} a_{i+d,j+d}^{(k)} + \sum_{d=0}^{s-1} a_{i+d,j+s-1-d}^{(k)} - \delta \cdot a_{i+\lfloor (s-1)/2 \rfloor, j+\lfloor (s-1)/2 \rfloor}^{(k)}
$$
where $ \delta = 1 $ if $ s $ is odd (to avoid double-counting the center), and $ \delta = 0 $ otherwise.
**Constraints**
1. $ 1 \le T \le 20 $
2. For each test case $ k $:
- $ 1 \le N_k \le 1000 $
- $ W_k $ is a 32-bit signed integer
- $ 1 \le a_{i,j}^{(k)} \le 2^{31}-1 $ for all $ i,j $
**Objective**
For each test case $ k $, find the maximum integer $ s \in \{1, \dots, N_k\} $ such that there exists a top-left corner $ (i,j) $ with $ 1 \le i \le N_k - s + 1 $, $ 1 \le j \le N_k - s + 1 $, and
$$
S(i,j,s) \le W_k
$$
If no such submatrix exists, output 0.