1 0
2 1
3 1002
4 1003
5 16495194
6 16495195
7 988496761674
8 988496761675
9 26688254956950
10 26688254956951
11 34018805387982
12 34018805387983
13 18069028755380465688
14 18069028755380465689
15 38281545036919307556
16 38281545036919307557
17 329813598438369669888
18 329813598438369669889
19 475572782847745049214
20 475572782847745049215
21 3955950004671759464310
22 3955950004671759464311
23 29909714452859312025480
24 29909714452859312025481
25 1637564062016157202573824096
26 1637564062016157202573824097
27 1824989266709079526986007428
28 1824989266709079526986007429
29 2326826985896880960251572218
30 2326826985896880960251572219