Take It Easy

This is a very simple problem. You will be given a single integer $n$. You have to print four numbers $a$, $b$, $c$, $d$ separated by spaces. Where,

$$a = \sum_{i=1}^{n} i$$

$$b = n^{n}$$

$$c = \prod_{i=1}^{n}i$$

$$d = 2^{n} + 3^{n}$$

Input

The Input will contain a single integer $n$ ($1 ≤ n ≤ 2×10^5$).

Output

Print four integers $a$, $b$, $c$, $d$ in a single line separated by spaces as instructed. Since the numbers could be very big, print them modulo 1000000007 ($10^9+7$).

Samples

Input	Output
4	10 256 24 97

Input	Output
400	80200 895205374 390998217 177856269

Input	Output
100000	49965 513479976 457992974 524625712