Bạn được cho 1 số nguyên ~N~, hãy in ra các xâu nhị phân có độ dài N theo thứ tự từ điển

Input

• Dòng đầu tiên chứa số nguyên ~N (1 \leq N \leq 15)~

Output

• In ra các xâu nhị phân có độ dài N theo thứ tự từ điển, mỗi xâu nằm trên 1 dòng

Sample input 1

2

Sample output 1

00
01
10
11

Bạn được cho 1 số nguyên ~N~, hãy in ra số fibonacci thứ ~N~. Vì kết quả có khả năng sẽ lớn nên chúng ta sẽ lấy chia dư cho ~10^{9}+7~

Dãy fibonacci là dãy có tính chất số đằng sau sẽ bằng tổng 2 số đứng trước đó. Dãy cơ bản là như sau: 1, 1, 2, 3, 5,.....

Input

• Dòng đầu tiên chứa số nguyên ~N (1 \leq N \leq 1000)~

Output

• Số fibonacci thứ ~N~ đã được chia dư cho ~10^{9}+7~

Sample input 1

3

Sample output 1

2

Sample input 2

746

Sample output 2

164015224

Cho một số nguyên ~a~ và ~N~. Hãy tính giá trị của ~a^{N}~ mod ~10^{9}+7~. Phép tính mod ở đây là phép tính chia lấy dư.

Input

• Là số nguyên ~a(1 \leq n \leq 10^{6})~ và ~n (1 \leq n \leq 10^{18} )~.

  Output

• Là giá trị của ~a^N~ mod ~10^{9}+7~.

Sample Input 1

4 2

Sample Output 1

16