4
1 100
2 4
4 8
1 1000000006
