fork(1) download
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. typedef long long int ll;
  4. typedef long double ld;
  5. #define rep(i,a,b) for(ll i=a;i<b;i++)
  6. #define nl cout<<endl
  7.  
  8. #define pii pair<ll,ll>
  9. #define vi vector<ll>
  10. #define vii vector<pii>
  11. #define mi map<ll,ll>
  12. #define all(a) (a).begin(),(a).end()
  13.  
  14. #define pb push_back
  15. #define make make_pair
  16. #define ff first
  17. #define ss second
  18. #define hell 1000000007
  19.  
  20. #define test4(x,y,z,a) cout<<"x is "<<x<<" y is "<<y<<" z is "<<z<<" a is "<<a<<endl;
  21. #define test3(x,y,z) cout<<"x is "<<x<<" y is "<<y<<" z is "<<z<<endl;
  22. #define test2(x,y) cout<<"x is "<<x<<" y is "<<y<<endl;
  23. #define test1(x) cout<<"x is "<<x<<endl;
  24. #define N 3
  25. ll add(ll a,ll b)
  26. {
  27. return (a%hell +b%hell)%hell;
  28. }
  29. ll mult(ll a,ll b)
  30. {
  31. return (a%hell * b%hell)%hell;
  32. }
  33. ll powerr(ll a,ll b,ll m)
  34. {
  35. ll ans=1;
  36. while(b)
  37. {
  38. if(b&1)
  39. ans=(ans*a)%m;
  40. b/=2;
  41. a=(a*a)%m;
  42. }
  43. return ans%hell;
  44. }
  45. struct matrix
  46. {
  47. ll arr[N][N];
  48. void reset()
  49. {
  50. memset(arr,0,sizeof(arr));
  51. }
  52. void identity()
  53. {
  54. rep(i,0,N)
  55. arr[i][i]=1;
  56. }
  57. matrix operator +(const matrix &o) const
  58. {
  59. matrix res;
  60. rep(i,0,N)
  61. {
  62. rep(j,0,N)
  63. res.arr[i][j]=add(arr[i][j],o.arr[i][j]);
  64. }
  65. return res;
  66. }
  67. matrix operator *(const matrix &o) const
  68. {
  69. matrix res;
  70. rep(i,0,N)
  71. {
  72. rep(j,0,N)
  73. {
  74. res.arr[i][j]=0;
  75. rep(k,0,N)
  76. {
  77. res.arr[i][j]=add(res.arr[i][j],mult(arr[i][k],o.arr[k][j]));
  78. }
  79. }
  80. }
  81. return res;
  82. }
  83. };
  84. ll gcd(ll a,ll b)
  85. {
  86. if(a==0)
  87. return b;
  88. else
  89. return gcd(b%a,a);
  90. }
  91. matrix power(matrix arr,ll x)
  92. {
  93. matrix res;
  94. res.reset();
  95. res.identity();
  96. while(x)
  97. {
  98. if(x&1)
  99. res=res*arr;
  100.  
  101. arr=arr*arr;
  102. x>>=1;
  103. }
  104. return res;
  105. }
  106. ll fib(ll n)
  107. {
  108. if(n<=2)
  109. return n;
  110.  
  111. n-=2;
  112. matrix a;
  113. a.reset();
  114. a.arr[0][0]=1;
  115. a.arr[0][1]=1;
  116. a.arr[1][0]=1;
  117. a.arr[1][1]=0;
  118.  
  119.  
  120. matrix expo;
  121. expo.reset();
  122. expo=power(a,n);
  123.  
  124. ll ans=(2*(expo.arr[0][0])%hell)%hell + (expo.arr[0][1])%hell;
  125. ans%=hell;
  126. return ans;
  127. }
  128. int main()
  129. {
  130. ios_base::sync_with_stdio(false);
  131. cin.tie(NULL);
  132.  
  133. ll t;cin>>t;
  134. while(t--)
  135. {
  136. ll p,q,n;cin>>p>>q>>n;
  137. n++;
  138. if(n==1)
  139. {
  140. cout<<p<<endl;
  141. continue;
  142. }
  143. if(n==2)
  144. {
  145. cout<<q<<endl;
  146. continue;
  147. }
  148. if(n==3)
  149. {
  150. cout<<(p+q+(p*q)%hell)%hell<<endl;
  151. continue;
  152. }
  153.  
  154. ll t1=(1+p)%hell;
  155. ll t2=(1+q)%hell;
  156.  
  157. ll n1=n-3;ll n2=n-2;
  158.  
  159. ll val1=fib(n1)%hell;
  160. ll val2=fib(n2)%hell;
  161.  
  162. val1=powerr(t1,val1,hell)%hell;
  163. val2=powerr(t2,val2,hell)%hell;
  164.  
  165. ll ans=(val1*val2)%hell;
  166. ans=(ans-1+hell)%hell;
  167. cout<<ans<<endl;
  168. }
  169. }
Runtime error #stdin #stdout 0.13s 4404KB
stdin
Standard input is empty
stdout
709409176
688276607
537247818
988048710
722453709
320988609
269473614
835013147
994495981
790250837
553941327
931760788
870667031
506917244
28091309
228993528
83051946
300722456
128548227
782759142
39546251
107695705
498981184
541041568
172046168
564610264
463783855
667646999
323220787
322542382
77815164
788473692
29822624
684017277
316260209
469616257
334847634
248100585
882682858
12365480
507597768
762137532
237982906
894586422
508998867
149254950
428433546
308310203
351380556
451964157
156798697
170165758
634304702
467705996
480575706
801518959
179570953
96260392
241212965
580440288
785919857
157551069
695390468
230611750
927040794
243438275
336728942
596471096
808458458
543104822
401501322
405963286
339482567
219758809
637194091
472249142
882631317
592707313
694021875
183623032
473700553
850383964
504475050
684995800
112658913
495023939
698006386
569865952
571725656
100207232
240679921
426725374
251491146
753843855
779541246
239326968
774516827
587194990
221087253
202332571
212552611
370233851
742562226
242485568
311929635
371976922
379575652
460302044
28358082
750967796
984290557
924989065
257305475
127946082
519400641
197733058
535152572
516763111
541228716
47626021
433739632
579464440
216533308
979251811
712321476
195971679
570607514
184138271
177803219
576275536
684291815
969720781
427572062
65222446
511243547
980110077
399917366
170030559
694374157
107814697
206576036
443644150
910285843
533932513
623885566
484139324
361714923
320323897
804696113
137588613
80475613
685591887
877002624
245844832
791480234
917153246
128404136
225569825
319010737
159077215
719914034
215157708
181640221
754202346
261015557
511517471
241038543
909186399
182186283
419974763
545670747
8827877
757792945
209906888
114590547
635555881
764400825
884611239
811501340
166210141
696107030
829904039
418463671
777521031
610133129
787125403
83275538
606618241
119361202
103336391
996076520
852589265
987257295
457709966
209526724
904683601
826895957
263063129
373147680
409657254
106339513
549167402
776958265
365307026
134368498
849514064
997201472
22261047
233577486
935571442
5867460
958045116
320888892
295401080
34926142
220856674
379779413
340783576
44654295
306387320
26810445
889084839
462690659
535995663
599098983
580500701
172522560
690097188
91963282
822633139
243144772
343722298
593457726
975976973
269985296
346055260
765488699
338913658
212055640
699820554
778898167
733770109
735238862
600551811
722771097
763349579
232349769
33682637
856251703
663471577
620689131
972823137
962663673
270629765
503821094
91270881
129655474
246090428
120799988
908111240
51892519
67658009
306254295
76267067
54824308
91095662
623652015
740561331
146825787
728682523
519601611
485418805
54524087
754964907
792557499
294579444
474381581
82790277
258980173
225930545
705414286
967496094
708718391
957451674
773761357
360500311
169992539
639347972
113330724
600055351
803128628
934140341
456203597
358081082
648415750
575680151
740956816
50117273
186604570
391499113
283910239
772912190
351612010
816928279
893813093
735271671
913417516
709568051
831721854
327033695
380618589
127560972
557070591
123891376
245971489
385525507
971968945
347947613
212572489
89895114
300621753
958160727
648969219
310691484
878281211
46879187
922001368
201841608
758237530
189920204
106060490
526059725
444326401
551496765
339350656
427569959
970631789
359968727
356883503
79794611
177179595
503028488
916812884
8999785
709284776
720457952
659068753
678213555
84951851
230397232
834005610
367903140
750691183
193779149
421622587
75764268
950100689
750359828
763586773
525757967
939841224
746575916
746189769
947078973
833991527
377980477
365793799
202798000
898918049
326726575
175064633
22562653
736929181
679859831
393892935
236733812
51755
65856643
238221503
672253299
73946862
109473581
652267782
64183037
536471023
313044090
440172804
659590796
411779362
554680199
912935803
805168929
319896946
574419718
353068685
990075974
86465102
556951284
295469803
932281075
870402775
294148921
79001869
366907970
541333623
112789781
12831660
745585651
377659711
772434771
248380538
834348886
816457924
237604182
288514520
594329261
190317526
287898077
849468762
825604857
271385964
528614986
118748881
137643733
412390114
965316341
83691821
150471924
737472236
119554720
961301440
257052030
541272637
948681174
539574516
700738036
701850076
463764595
855670236
165620390
871164605
610183769
929325566
353343992
671083904
990289476
275599403
869104702
483723859
736466833
210733200
424256518
111358797
834395651
212725223
911282353
254154685
458482048
384554093
578093527
891857674
34264562
139078616
791094
799248486
412899551
954456228
599047585
640920111
612429068
747908999
120144178
23785435
830186641
367707153
640888959
862003668
24817940
508212242
728993703
424666708
997448223
859446732
150892304
443217049
910826984
526235927
343747919
413022231
169928715
71923752
637212594
661742335
96114041
230263001
230117844
716278660
735006044
18073916
526472869
481420636
444072314
132432814
775782838
739144031
186986696
91735801
492552375
974357587
947262355
322425255
249085667
854325225
372619932
40659935
261024686
993547309
265686452
138964503
650369572
247994401
206114261
263518349
926751741
733984365
514858291
388177333
925786440
334190522
623062549
994331238
979285585
748693788
460521692
305889447
912952403
477497731
282418834
242601755
939622381
709070758
457158343
694159818
701331030
188365444
910939045
566539410
965161843
930606123
398372342
716467182
125458270
189106730
446549028
252382703
309342832
109050971
383744723
859137589
14916184
571594385
546855360
704515731
709360310
628812096
566101779
301810383
734815964
502259161
110822496
84336215
979226908
177448768
892897799
171851450
816862448
572705266
560689642
408446721
569808668
391077650
232080480
572366573
436198168
827946262
807650657
569958616
471754643
287701496
345430455
868308879
711277832
108897530
775511847
819548007
879907247
275278394
282770788
134639612
722026606
630844711
253615180
348415156
487154812
488858604
605861190
263772563
443249471
451333435
267524218
64644057
669461252
882373921
100546078
241319530
729161415
700689672
564845877
780746203
6538207
41229664
374551116
985593749
386632090
257198688
205739973
536213624
748950290
335366722
341451792
539651684
49621988
798241894
627878355
214532984
986668347
419748451
937109917
446815651
679304821
412002887
537197113
843977911
810822838
978486045
92976398
463998534
603931516
83382117
661913389
334805948
190578223
783067924
686607677
645635013
449158637
751701575
695180716
971910317
499560812
204078400
102826507
62053674
777358598
261567812
233850077
681388618
97677136
670401867
323655688
658523808
772142433
584445950
987656128
533762331
646305798
340757910
696394605
511114282
79732302
797258764
991804958
366356551
246130836
152992515
918074226
440137871
781270312
871175799
589829455
532482932
83692605
669604
987048349
168591741
799934156
356631818
749027968
98227587
224382301
161063851
627768164
36698757
903085449
150876301
710742189
91990385
973457608
193235297
641456319
140759672
404981699
543991413
42488918
964346223
312673659
84860070
400847651
970791578
99848617
141777074
451869320
388387703
431362790
271589949
3245643
142753705
706113374
431815649
864943128
949232343
336690078
326767702
322527480
397167535
12187353
441552267
960324905
646475677
360849437
818002098
606790202
616073255
454320476
573600260
120218700
464663105
307458473
164935995
213808887
824539493
90165574
66303510
151985766
634529206
422453488
246569848
87701038
132000348
337313320
782670703
567611219
348643398
833039732
982135859
285672687
857234331
692350900
662297408
820660043
6378876
147615454
637358785
267524793
735175151
238658544
434141514
568714607
263810928
337019824
751150423
557695910
513053610
987794670
335565647
544772115
279407841
41306411
678446782
714167731
453066291
646110829
960012560
256214073
874400812
839900940
584832438
567502655
62100131
867085560
569411863
40197044
160521161
442399654
95948783
642135563
365889766
708286300
414049458
564434088
759280414
668060359
835133398
92842344
804115233
817397380
282138398
903899361
66628418
334530329
419711843
565128048
940787915
590065481
538071705
164484762
418883505
726719406
951525551
54343103
889677154
637025736
194353773
84807650
486757680
121425952
881759894
606025067
764411285
167675330
834325093
886464333
807500685
808789259
707747220
710906014
993221028
932660620
35505343
976028792
806790132
204146710
966277712
640715037
423195833
160786027
369349759
437449319
741053537
6240305
807131827
517934043
465144184
848956020
362339606
856151030
644554282
510510853
580162001
342038911
426459331
454233497
773118551
595140171
798812273
408117118
604655878
865499907
997141990
716126384
347974746
896042329
633479938
288222008
133899145
296677776
233134713
103444780
88137216
674448859
556557155
761456807
510758423
475707259
702157823
204451235
978971232
194230848
401141932
890230723
470793700
362064425
641259029
494513609
883539702
841733504
403457129
774916982
760918336
629959172
656937157
934872622
248852506
555116353
701302409
721827371
674005273
119975881
654751035
161544475
140338625
641033472
63698601
963245705
212600591
967850576
98691177
903481521
361084445
93162492
822901203
560348444
822247937
237538959
229151017
352939205
890438537
464542052
936219257
562532094
895511877
767481746
295944627
261390214
133171938
87251332
57304341
397062910
344092782
115685945
611493612
766279068
94531512
88579587
402656953
420492324
579678950
717765750
281815224
33236294
444012961
228518124
420840596
825710905
99001102
626968433
38844369
658137228
285032084
47476814
78980394
762632298
465524520
367655926
518569341
802034071
33624338
337703352
314407769
899169490
423067329
555982202
504202661
814930457
797416162
396886944
805651803
328343339
175336272
96978340
917878788
762201424
175969119
540564307
305436863
935046131
254227155
67720590
855342389
625447078
812789525
319996736
789048905
914328040
713013203
485652547
428153529
324157482
883613606
297443577
499298254
208382491
633278791
941980096
740450732
137544054
771938362
818975545
945440372
422690294
61813460
441082675
599847713
31525632
251692971
104203907
114942838
645524124
675183712
582940756
507573016
691558896
326365817
844891492
550663397
609958750
114322205
165067300
976115006
771606718
645693788
521416656
849771642
602430927
632357901
531664688
950105929
751513797
159749694
196402153
663202794
427506541
258420029
772583753
744317410
532608148
255391877
409841212
389529535
402675064
65121514
101963804
803428109
94352407
151375623
512308006
616160797
102630414
962813310
661252191
988148482
915658663
443759720
423545733
434912468
206306670
337950551
428841113
182105297
770987439
266325423
806446562
553479530
670670162
674518124
224516711
274660434
351028720
844152582
410847293
3489297
315612317
474087971
455240515
745952600
613667207
751641485
300595663
998755925
774725500
865368589
744451826
114779122
110337515
77275788
757585870
253487951
559653968
437422728
702023852
817595513
457997302
735702982
221468331
891981668
512593138
442603230
640568158
932249498
122916953
660993727
515022197
137894531
465690127
936022420
997542557
653637566
8619127
302690847
572539016
355700182
231991497
619234705
26464642
312785182
715280148
622521512
228702248
359126086
366089845
482052858
679847128
923336067
537857181
699026621
210031900
240543198
334979696
58731848
922275963
274808631
219175489
51070155
193661578
981504041
746014994
309932117
920805690
80372745
400043718
663671367
65009111
995746213
696373935
815465460
386771139
924602010
556249493
584983330
589407760
933475906
440928646
599811326
9033301
821883821
907023329
647548785
51892207
58040335
167019000
289522489
354171098
750733030
594551831
966585826
102643736
720017638
218513280
762404946
126715935
264624468
173852171
188978950
863650771
780417466
138777522
72687808
835784183
353276807
633562509
544835837
774153416
369626395
824587466
246742316
876258352
932117938
218743600
53147253
641842306
293096630
749057505
897038682
656656577
298180391
233401888
89463141
698751533
635686142
484828906
374171297
723415959
426172838
293008822
691950567
347438022
279462920
515728815
177170987
231184926
213527682
76880578
797775927
137927998
314579309
451375631
623806631
396896826
56416188
208132077
283608307
68908121
751077170
968395649
39775709
711671859
553394974
208027051
478338612
411803642
347365363
557649470
61182836
448499194
950233050
452642659
937914529
123344821
972127686
558312771
644609881
779377710
804378111
320661062
642323889
638639087
739786727
329537841
89423467
462597143
537935372
732221581
74604876
893154775
869503325
309525893
72031149
971764785
575102561
177930833
591965791
722121298
845153046
881326975
985234224
15459856
520564130
984127175
581814927
346408062
470357802
885602580
207219487
121699743
821627059
82765012
942012660
431344963
251131152
391794392
964282696
102304687
961638182
265340209
817554755
125027716
649884345
587607202
76703598
952922494
474303807
823922939
602513515
17484111
907172304
36445222
723714342
478100661
32568468
826743149
410542842
427940544
749453952
854172274
560613593
630882254
963535442
966187023
837001796
555060083
249433479
392058350
722814715
941632424
181397653
814830789
892769309
843810585
680309171
68130252
682133070
793859896
115621181
495514563
186850794
189789118
259631937
432355409
405770560
6504222
598552277
466018174
94366327
824088222
8191890
616647939
445748994
799864463
489480746
99474473
750058105
13834932
784988941
342289002
814117759
74058066
865654340
867929025
777516204
781064190
798894913
554917859
469258337
887317869
679743643
19679588
722821398
953151221
307297639
516704126
231295526
253493411
954572446
897374395
68604942
285429733
247250965
320871203
99205510
767589956
389608955
689435458
530099214
50780333
667469172
651191819
517211625
567490495
353519624
322108471
716830675
112806447
603652335
229065234
618104312
720755098
730043058
96755344
423991899
137270562
804342823
920433634
49037975
186769345
642572165
787177991
903120018
115008461
886511896
184162972
204275562
729988840
435160322
612320403
972975903
741522380
989887272
729196042
144969199
42816472
897091061
965792407
633143730
146098209
124313354
172486947
508248923
851896641
437480730
534893383
1344874
734771451
583197093
426824082
518726146
735782268
757601056
604750799
47238352
567460382
899342653
219114537
377745257
108974464
36228286
194342625
396962795
829457382
613676834
1230452
748685280
43613738
403368305
947804673
31353900
284651944
920256407
602244141
658809586
947806651
294501997
592591350
822691979
157474647
176008523
83940695
903072764
902112554
682351663
710635533
728105230
672652081
686485082
554766746
694061349
662633371
506014736
370962475
69336910
1350945
140637371
582303996
634959984
537460637
126854228
374084023
704519509
907076972
38434644
200887317
899428299
827756623
926505110
810553372
94319423
363730334
816126402
481264254
788108768
916732062
872122818
75787496
32961003
974280770
165261179
913231425
2898460
826853318
360355283
84810145
16989487
947659087
590965249
934456904
870643461
581976796
265630396
774881666
392406937
377107690
547617077
65195437
834429208
689970854
246860294
102402895
469229931
590329550
44772826
945815942
146676444
172460201
156270946
299232555
286010526
146010463
577305140
458473646
573364889
339944999
166662317
295917852
973334775
382655329
883932325
767753847
907593374
732632968
886075106
427113932
744993565
967762534
472005908
831291897
213202486
835915839
587719582
578151000
973369663
822675591
960668881
561032101
403614571
356984207
552348467
504367798
136074478
330960210
483154204
513003542
81776531
726098558
814786323
608000918
770965319
299315958
248103162
644449671
299427511
757569061
907487315
946627428
927274643
41062516
566385337
802458436
648281983
662393937
655143313
677089839
849397875
988558200
177013232
980919559
706543649
142452210
67661536
238919280
658235381
95344480
477770992
22784921
733165727
602872453
755669768
476939291
348300557
62149565
182865365
53776134
846667959
99210444
490854071
857432367
391880557
744503977
48260549
867326122
716172105
749641640
340719649
879511105
109765901
731108440
487403893
430875596
389550272
132727022
682200349
303744369
37013950
149006416
59638784
302438708
15469025
406726138
529171505
998800086
510321744
368013010
641588914
926860538
401780182
561356549
904227555
697933400
339787899
502801322
463471071
514197066
96768787
618437213
77986232
164633872
163198727
235618638
908722564
165035076
739435808
970107069
550373164
767330291
150729397
695118269
821239083
330456670
298013948
904369456
348952715
692839997
893859303
30265536
648634330
68977294
380554561
17153736
412501334
363207321
52670113
153577252
894449059
310831491
963879000
648511982
467479721
404345332
513224912
949120181
474569779
406166847
116457289
345802383
117140451
280885438
54357098
508504641
973667705
800689443
900219113
136876843
185131082
396653650
235751799
515079709
987660210
749676349
839731377
32823049
813725091
398002677
250790506
352135350
591727542
864031772
588720666
524839850
993006087
619828746
993318583
491361195
26719035
797675396
749782739
202221699
626050816
613921486
939927525
65809876
406996452
220645930
828633989
901951677
832206849
773160896
131535919
394343747
221055932
263326357
447904349
196121079
243793611
49283165
827638529
388232728
292744611
410617440
201511865
361474152
285955093
676127763
957234583
372900057
131512022
443518577
511283562
229187114
930633523
664939598
322135223
585465963
712440497
17221225
741726861
943786236
844762855
906780674
708252708
680663177
180239224
609993880
432761412
507520587
252023568
33388528
183337128
5543741
735082106
507166221
76221344
218135059
774234938
690646858
1782041
950215130
630312123
285023452
792668019
853856751
116848243
400341860
43362460
868793549
694202565
585403061
156656493
313917148
208191830
95854153
845261811
330614062
7874075
80169275
483835084
196327503
640248971
955239425
114616339
688472843
169383217
503010891
979599241
71700268
890644471
889373422
193859036
703094048
217577146
863876310
396273264
639935946
166715209
347948163
412158344
416160413
96028975
354735311
87324405
698464224
188904090
798022622
140002533
542416790
782095058
95092622
75049466
540608465
472490494
971168056
628007421
768006929
811236123
737094599
46542021
474856684
354235258
310689780
270787360
432580630
834121617
773135666
162887504
971300937
287490194
114626451
268986759
619657426
215954512
937893338
283964275
518343362
793893873
816845474
355899952
520959307
967123396
124905751
111161541
949898292
417967568
423878831
860713096
689596290
151511341
252086971
193513030
842928673
826909046
271189382
841652671
222250506
920166866
141899355
925840063
640322013
136259252
232115651
521622106
308191092
163977948
976452462
19307229
77619672
622881818
884995009
775992110
409040709
302658714
800781589
664256090
998232131
211890605
948769967
66872513
523733127
229760113
392087621
349684374
42278925
710491296
586411790
7866604
447424035
711359945
310017552
108696830
329589067
324355501
476087327
594163930
441216320
811939021
827746426
697817060
899082028
560977785
755042087
949062164
562442471
737953640
580022644
743991711
631593980
923780690
371813545
340453515
357671858
559205881
978589202
849554073
726918663
72470089
211333579
242569110
133103196
941540805
502434052
652005270
796382916
983634521
802937539
304196057
389232147
239652395
215463695
211986961
336100517
619351916
670841519
502261666
884724003
991138012
619889481
168307090
575531436
710409607
614800883
657195055
280460408
302772519
99375375
806850595
597352180
981322032
928756673
518688765
963195795
224405982
954909597
515312858
529126783
654642440
525758910
465253092
267595007
135931957
133842672
492496422
117919709
989890701
847221532
180289181
696047295
125120549
981984016
906364121
577996277
361612320
384622408
8918646
235074222
999060479
422033491
47379099
813474710
705074106
470162808
689894614
831834025
31341770
895067003
478775534
783532317
57143707
891645856
355859019
318989306
384892592
217022236
976439398
182552135
238082863
843993298
402690994
984281512
55546341
54220928
374118218
124005095
445898691
860339237
215107729
740216806
657838940
3112887
465518580
64809392
908940255
926134779
131095433
25570079
355774939
614114848
8892451
129832140
36909024
704428685
933430912
152270295
211561823
337277836
891008896
474764312
483326368
463403366
186658967
882152172
179751029
301756934
496205216
364796346
752281789
830935605
780121787
63983382
798844993
283648357
629241187
512786707
357954501
234913209
418358958
651501040
392247253
521544969
629330108
753489017
418148286
972260599
561748492
10038112
905420728
526623371
348989398
467855272
200157611
549774524
292143414
696403948
242699509
623358
922795073
610506941
592264718
960053635
970227039
659075838
322052366
916110403
988138813
764911168
20048231
744692903
1818647
250993453
246644971
500334691
78377792
322894429
618238725
212771768
745753349
401074892
493653494
716709485
31151764
662427720
549627020
124143978
979204400
790585883
781129646
723084161
710098922
540164282
916376704
449756595
768245159
818206045
322157549
109802842
318148975
272601046
676241838
15398602
268929331
996511754
363179496
402098789
758090132
509408204
29416657
473997216
654639485
388371571
81898073
253417358
579164305
637699310
153332216
450543550
46302679
573995691
110335298
929104009
342619406
359609317
422370515
379616496
766271796
145404608
250576222
158322415
789968661
42773194
897848123
309704677
189849737
188030968
991775458
140399138
516739624
464667147
126556017
511550569
448608609
273002891
682933334
698850904
439269074
817792590
737903193
234757777
164990557
257965205
984592193
373268281
50790489
801921476
236621920
50631923
12313880
580428789
499501339
350103907
987031716
511352214
230157197
57217941
518977114
128766857
4665305
791023395
56555537
709104891
384765239
15227231
922333891
342772468
865027456
56564083
397547992
304224950
807327541
364439365
750632416
78535873
751527746
16371330
415696693
375147054
717852226
333046820
579428597
604774503
505899911
211756085
174324247
96486893
373555227
239146592
724098498
820104097
228695907
677916615
479575024
790332274
296088851
182619140
477805233
131264888
282797837
554659999
242361156
400103957
751185906
480652741
474630019
475794656
987018164
993872887
881702740
570180487
269201624
419219207
234831562
388380267
367185637
493937398
904769518
130174097
534879332
370787434
764647561
736110513
976305569
923081456
241449520
846081518
176583428
896360419
491834473
99848735
103180756
93855875
266789291
844267203
18644715
136506209
166623508
258545815
132938278
790548112
873258798
877624656
193284268
682867247
964904626
869881391
701088798
60339767
182933886
74550299
676758615
748608453
569516383
128249483
933132297
884518093
633064417
234440397
358882419
798507905
844209698
254623495
411798342
335897467
295340232
884400902
929036236
171038643
30344982
118031983
261432262
822499409
94544944
468320164
644124936
610809627
200214732
727797728
323243524
381081708
22636288
439525664
453106290
473395620
505461986
184258167
177718554
567342290
441118747
113838144
822764746
914240237
616619122
970117540
358497565
791318635
475319680
999969889
265755844
538545363
639400773
165287495
378375748
830774528
153360898
790313884
23679942
617906445
318188654
592294396
226236542
877559125
184863276
109669453
255661889
896213326
710057449
171095534
146024047
406756209
958782388
678150295
724757879
704934558
943226815
639847310
828021911
44541833
147247654
559988509
115748363
906262233
701032768
815651557
120657419
918359482
358555223
305768514
810264043
757502042
403005243
532772440
359570002
644617406
173173326
76963102
918243003
200592800
960554559
59160043
818107751
266266057
619441347
579870920
227934676
154618686
77602792
812866821
213778117
87694514
244392593
283466228
265884351
83963969
532841503
290572412
240012935
476546608
322097526
92337280
550604276
244630864
612346011
848756420
986769141
242412385
234478695
255214960
472678929
920514302
745981805
393962798
79203815
470736250
857957516
621373429
400789302
723046849
503219913
854668322
493990704
821516766
529449616
602566100
386144866
716768159
645933389
95985505
615814550
144355485
86601664
351974214
280899036
58374405
158032911
301874732
781269501
555458110
362546687
56129888
70769898
591267514
170937232
878233100
360515066
16159462
845348917
822296119
408618043
965192351
98617215
992439964
236778594
944814707
509863995
188060696
895883789
799037933
551591325
75693958
461367361
938707110
820363151
499034809
411796378
314447907
997368529
594698690
847276329
419582594
578319856
940253056
330841892
99391207
57365772
906068707
910281666
80666069
155936781
761445034
798308183
851591853
905701320
620270687
261119835
596206160
297580274
850856660
196787337
165693705
32949888
591240758
414985512
160438322
154478822
127643567
670044293
902756548
294373315
336538143
452715096
719334347
850677143
454293123
852653483
37393621
927246223
558471669
593588878
409346648
900715582
340732350
171600847
981671970
502241220
885263715
172841917
923028763
411081465
809207925
730115627
823060019
588744856
795103567
582778925
391406924
297289436
278311611
862868736
457849334
220764258
577896734
293870881
30581115
468556018
869234448
383367775
867176688
166920245
240100078
970756492
342503996
819393347
840693497
715346910
780395376
564642756
567411118
447307685
436954584
935268315
6913475
168494122
677891235
249830605
106463176
280136982
999434186
815564753
525686996
694090631
427791184
960732658
797476704
487012540
128614888
231931753
587476173
838416187
816343004
780759325
907042766
152940127
319231922
470590427
112120320
477548144
978518202
70059431
511979849
78454026
115697964
103208128
137723564
393893426
808384209
580667101
237444628
547253727
752114859
712671495
343977416
549201850
966034612
437916355
533533749
967512928
569448170
981263617
627491301
953909975
641037295
454007277
969365192
790591358
936565113
28722652
432170502
153806438
641974581
694754736
755990787
471588507
213174725
136966778
380042568
731480940
841036700
359433243
823706110
506882584
633773662
892936179
831195671
997593399
345698814
272584342
117171493
243372321
367374981
788185896
696110414
17166398
349432542
707366588
432422501
684236184
502740514
620582531
553740126
678171434
915957113
683868993
856780333
990085495
671145081
458082273
597199416
18623000
131069450
499985371
878670564
410572734
585123012
538600841
269342730
687701961
262545560
150219009
977239278
665631463
900951006
791887461
325411626
202164992
639010960
276594378
564920119
341114691
463161729
961533051
349541401
712749647
492977932
757928668
989566441
21980300
700800759
769001044
334792871
437393131
915151201
694378734
510086257
45786146
227983737
956202675
472348715
513789385
178785682
825576674
675535008
890791164
742178536
664057179
443401392
194181535
825762856
410786532
732718974
98875359
654136843
581169625
159574554
799287248
61175950
706244787
373709504
142398611
476899022
77331294
887335132
453555816
461142203
604054099
176558757
457125259
591060810
337621363
909941462
747705806
717532025
396577487
812910459
989841769
472672572
13676838
211794694
154048722
537268788
757949156
309067320
384198602
129949938
674249128
523674237
396605073
230020302
654226895
598423741
413471752
954770277
931187862
433873751
554273099
948759794
524455151
15140126
517167363
586067565
685408489
319082782
650037784
840174106
352809308
55413354
450023090
62609640
971989849
379384103
626340325
952535501
336486953
401230538
991608779
245743182
182179067
910969538
214846295
617649515
301649129
921063513
727976784
2977510
644984874
273351490
673181868
658604911
496404786
128328557
27043387
961181437
384276729
345820140
21384505
828369001
256494394
419573295
981174273
210865456
235382897
336438512
272401263
778978256
349954227
882991161
44247919
3898230
435370352
597332665
834424580
55659553
233330326
974097460
752332405
691352802
34944219
425512392
284817036
377562433
496939097
38632896
853919533
172384302
552086184
88492852
378424341
716906394
904403293
529685878
199768937
926907675
381198283
44278692
223736694
226898710
723923533
788681737
325868409
693175228
72214266
714392162
40464378
678636581
944181393
763431555
240648002
15425786
905134039
936584221
362488550
381911647
820745314
822881887
646719576
803104621
790900554
816634007
637940444
606302186
545293407
756397610
406012632
243635440
200092690
557138015
16581057
846317687
190974669
8264379
616103298
746547642
164440340
564164216
574078511
983961086
122794359
548647614
277855575
6579217
65703843
955044022
61073970
556127022
812421383
271396728
214611135
651610141
912420890
186477607
51886279
314688836
665053380
757468968
384955522
38261379
445499236
825749722
662394215
274999657
862023624
67254474
465573629
840310886
250523700
928208249
460966101
617211253
979219616
759636091
953554292
786931602
85347657
950698803
969470276
67621520
618065972
880043012
434741398
495609551
414334890
134520267
188915707
830559606
515711081
296581621
112282007
820951522
275950531
988711036
372287172
302037362
224532353
635622388
752749729
176226461
253591439
975929319
864609566
293739899
661971840
502837188
65924424
660698283
388764542
321075881
220097168
83851406
56059527
132825602
558372403
246898853
614632416
387714310
567884538
37449816
818968198
327779688
345011068
35588066
976682848
424655104
630173557
94578112
260155280
65288297
232217679
497763496
826450292
60717125
221560115
461859723
884810027
231952743
825559353
692455351
534660845
241982154
401777227
260268637
863164236
380858579
309398938
736185946
104694729
401905967
255303293
930134397
1640398
762832135
64302820
950889856
612457436
601809934
385577912
711884449
303372211
773141693
752119737
42948383
182581184
798277350
341993986
29748690
185951952
717306915
498457303
987086387
444478348
497907292
166422698
995467053
455430095
132416269
22652906
714299802
894210558
221026309
417649441
392638421
902721341
791250131
2794751
936713920
85817410
661724667
234180345
312117378
765063620
580540304
885346281
985041637
713769300
489507705
566654840
228338564
669259553
34391884
727599808
593995091
410133742
350133679
723552794
14254192
113423807
838709595
506184709
326841684
459846840
151143639
968240261
428138366
867273276
958327931
208347763
413285687
385251595
930475092
53614671
188718227
303969127
400656792
142975438
466518566
451571040
157118111
149857445
409922362
947455478
23431524
931195537
687900069
289901362
504833247
219484702
363091562
309009487
64786194
801046891
892989246
891486538
599630923
457397263
63752570
344243986
689638505
872056017
865334217
552942290
632254270
218024668
698947022
211899424
373736081
161595814
342937527
647774816
147934721
400348585
358424899
897727099
792415798
750280329
501532634
129769536
459584800
710263200
604224817
117403955
908335226
379577164
460404152
926653937
820852433
859743696
679274798
883176348
749092826
380881181
792758004
978455953
773943384
905638873
824756019
683001245
560472540
528693669
93547915
342342194
676937833
347894955
108547503
477274656
188578661
593542228
601811811
944201304
712865704
619561981
997975914
519169339
583269444
341553514
912441699
281006972
180578376
754816346
306734751
690946064
409590703
736114730
130753397
861179718
759719950
341085905
659734085
811201661
549168211
586782604
764855802
797359429
421608707
246900235
388094035
802616317
338607538
148408931
878371673
124884760
808793268
390432037
125900607
622789693
193955583
660566092
720784975
156535983
680774895
827299102
431643547
576449224
993035403
837720089
31477740
919464975
170500455
195548227
968434095
346992151
344470697
987753906
569125196
986902630
355995256
297492595
475758504
621797763
271101907
30539798
720880712
923887829
320110801
691519063
312895143
594414530
971011537
638525047
761649593
81852065
400563059
794773568
859087547
637993055
141711742
354778858
136506926
155882631
819673080
175709809
316452409
815305189
227485434
168872423
282116163
130770055
435512922
488461560
285855594
362812920
840079143
972278668
88480717
354501492
206573075
342989226
160285878
450797078
758725438
134987108
818438786
977245994
383231974
183851126
506491210
306111943
132823127
211876538
743799881
801806101
879797010
3174872
252050633
373458942
697205927
700523202
735714154
872672323
949284587
249480614
583232459
596742189
837201923
51408808
504071644
738724750
832194015
649984612
274047117
345055238
378940485
524109183
837260042
810137536
658231804
544956261
471360122
629281898
39664139
583341195
567982454
143711622
872194711
252041987
266126608
853755528
628660866
310124833
551975889
29991124
798095610
687967297
600941672
135412041
831401037
248071270
381826163
47164578
25030710
969060870
433615306
138955028
137257713
831945058
28766498
770126712
388103616
961899705
238309668
943447327
880786105
428397723
499978476
16076477
464849380
794648137
476360733
213213040
999083933
430419748
848672404
993164415
587041890
761346871
439072476
434206129
846574151
908279330
839661958
24068124
845493258
100607771
216783301
289450851
837339426
430880773
880922298
369972072
610513103
183239169
833997147
37380183
438248413
119177766
2068422
172104312
758458258
690633514
727233561
634267360
971546325
322574950
384984082
640033568
962931547
54975234
589884025
787515508
289093255
508941562
265739061
617714341
677971407
751994978
576371400
185732268
172541749
500404759
798115009
205963962
206450688
462145118
283832875
336928404
842607764
219129235
416606265
71179245
561726469
52159792
96361978
842526806
914758209
484459106
405896314
961504781
136779614
982019165
507859675
993151570
922713268
637568361
131315298
250485481
866870549
28385697
821715612
844871351
27555471
240224115
427913167
787994060
549114676
375839933
86242793
629673536
793101462
455659818
549523934
1831979
141899047
36022557
108490636
118216337
723649750
986333765
586235509
431221182
728204696
854187770
607995592
727096430
639528628
137743412
742172469
168417266
165076883
817847820
821969235
942957280
139544741
786536702
841788739
773720040
622325551
373041234
432532544
635025763
920804230
192066641
349571876
361013122
572670819
910659706
916348685
30611130
472470582
808619366
359079646
304535362
439794858
93567214
839895031
486469413
392822855
871075382
673052817
114621134
374085890
371253082
184194089
768067040
342836916
542500458
844240211
885042074
632767199
626626813
294023094
986285032
924903109
327542006
404664721
278164195
85583619
780237576
972043314
262837374
170824315
244658700
959217937
14737148
929470972
187398619
408497706
338183501
72599812
611006908
12297553
468401120
339806121
676651899
473418607
356178013
407735425
253539212
296621311
825690512
926265213
184028011
241321119
828172265
795023244
862704898
826428055
795750830
720298886
962125359
185224929
868292937
922456315
864926724
128074216
548554276
669497753
971300486
976810890
493765707
266838602
801622616
378078525
322088476
773321756
399849306
576664542
637984647
634871338
150322753
723049181
554852026
815031606
507910642
839475369
991571208
621637523
458830726
70815182
671082773
116297698
302806452
79956965
548810604
859085277
310907907
353451797
325781877
728879320
456185046
330031030
667153461
357809920
862097626
883962637
621012711
288390038
659839542
201245688
765475549
798021130
943893721
301509671
510309200
789174998
894967168
378303933
487851888
921022891
264591854
785878588
404244365
869735328
198307185
483816950
570049877
980641723
404935613
640380211
262240451
23733552
811359341
270202350
89797320
25952513
35683621
846521580
899797696
712711815
172412629
768472460
718707314
705100802
63524372
549416961
782305256
549628940
988966604
492781331
504007920
910370927
516093869
39076697
718823521
581310938
812043676
81533619
120458719
433416354
984904153
154307904
782843955
946679116
275717572
953651768
65877798
19067512
390025505
784642959
680561205
466342293
895912636
437555620
166733775
64777965
132862482
557700611
781128596
516050039
452641899
321858307
840683224
234208576
456754284
379672054
802087822
305724653
74627016
131944981
172926036
679579279
631698238
571977453
985047251
887447122
843607300
324548986
341468474
938961054
290861945
763756770
709567308
655906905
493532647
964562272
570381356
666783064
259024940
310405012
307805379
311559615
324236004
504042171
685600846
937986259
914386521
961413810
689328573
573808492
909996817
558113993
66097406
185194782
930270714
329903625
315302473
365617363
599598129
71788305
866079427
562348349
298491822
829591233
674682703
508640130
271899675
851403960
840180478
884073225
292287826
109197673
311747173
38578813
718861265
813114808
454735520
905055073
954693129
685546320
374070223
63748655
620897879
847696579
860459685
314737596
995640735
510130802
433306998
399043740
672084150
4512086
139405622
294862130
927808186
710506340
80119766
547231669
588512378
907158226
782037572
204040379
817409019
648122750
513072186
972290158
784722494
697860346
637669804
545615179
500091822
112669323
413640869
437719713
682566619
800468322
822567588
970636069
384573146
569774725
654173723
956563016
448542769
160660567
696051414
636102542
840154645
546446631
150718186
515130014
193303288
488361688
522240843
855328589
537372439
365441592
566624626
874433382
3464912
287590916
166673293
187555754
637841615
21884024
257624870
39060345
529024953
200408934
812902455
162726980
528799071
969906256
346131611
645714968
773991753
941919226
528790194
233035728
717288105
838221000
1332075
35156028
502158393
938480167
664870361
886735773
821796650
382346249
786466350
951116550
4527294
725205887
494621738
472340536
58574856
36067875
332102520
462867771
894816347
816221715
978416735
630804108
354281059
470750321
317675979
414921541
518428974
36454668
775670094
368485982
439013499
988459426
269605883
874503574
916212054
824496945
973992895
556316481
602773792
616225274
584702326
121092746
729049902
836374962
459488342
92712253
668053728
525045936
775639474
537419308
256572461
711876637
186703587
865869236
77548055
609527946
345549029
561564817
797281555
377909965
611282594
75773288
802457574
52513371
427607317
2870581
861526708
348687687
701438756
369921211
316873972
322886454
702511845
981312518
799971479
335901982
594460811
56275415
209470515
390853064
438771034
831253633
784581091
442462393
303903479
727411687
914216829
853225025
86158868
909355097
702436857
562341728
237990301
975089025
716731251
762151573
22985711
152560171
691952593
8767662
113700172
597642505
924344579
331724230
277708511
970247895
583168072
627300425
10291341
529253561
228855517
618498471
200940986
850566677
295117621
535559743
830306163
760356075
318354139
974317125
563756423
950774685
419015179
900835058
877475349
51690592
144480334
570355371
638773681
470623717
26345124
295942134
828255154
363274459
34326852
899783903
196055622
314619173
734535402
382641562
952551419
817634569
414238883
712873841
675771893
339738677
48335865
183312368
340350438
913273444
756961249
893272680
77900274
2130660
38334960
805767474
170990008
918854989
303329920
262690388
692528148
580816551
849499591
497022843
237134747
37153609
960989138
572452050
379216347
555249178
69410223
810213159
509896104
268645014
408649629
212622654
229050157
190610362
455972022
71161134
576298953
689441093
845182147
777911139
827996252
526068632
815958700
207386903
607717674
242099397
241563075
956417447
510284015
460799721
22624144
826755651
539828357
160372736
338329797
334105000
707856065
994432778
652830091
29008100
112013764
585765122
124540600
492099693
606835681
776705254
638596952
375038389
478512359
916638442
185431910
995868233
480718314
676563510
860874347
335662658
691827741
824140818
907656358
840561477
765517286
845509916
262668007
29338835
592535682
517665809
24491665
4898328
118493168
521951674
534224710
963494099
919941443
717486688
369706256
690348933
626495811
647386476
291139989
186759099
354299619
849180633
943836160
989847199
561608062
383315225
28452265
347829406
741310523
53610693
230491410
69708600
448475898
47111484
406783578
891025933
646192466
211009741
789543185
603169634
997126307
505867241
911353912
228049336
177170102
414182349
516102827
323180519
386316637
179923614
778526990
615264741
968216635
96446838
559290598
489186948
814008837
44279260
256967126
234200825
488486758
215678308
206259275
551844726
19558666
29257579
876740036
796085714
338549956
898320264
979547311
245415773
10220827
198491203
441395703
704698493
844756793
360976383
240997381
816477696
30503175
717329537
994446891
536824344
616380446
207683012
497054862
925766637
199962951
167254059
222912136
837772756
276003710
429367505
701544270
313219325
91810395
717871859
213749978
962787647
100888525
977787272
341332330
889485263
808666621
787096494
672099641
805903913
294264691
374761032
59131420
630798417
186597311
64785899
355439340
440899700
73545354
267485328
170445336
724819490
514289588
86034898
922773096
440762898
752929607
441969553
903917041
851535439
347473374
197708762
221931804
554960366
348271493
386470089
688438861
94210390
971536134
584712869
914034858
944799742
277060661
736773668
524195945
568616503
23171255
243890058
953385437
95912238
348486364
764717499
660238697
501771212
45979283
944053931
546896226
293739286
942909306
100842928
316820028
466581527
65689235
648581157
227390843
887747446
606371933
286408286
686127442
745910688
194568283
293345625
111699250
413160122
479560073
772783422
308560265
446059362
578539068
297052281
734805510
340796537
499186713
251982805
671855705
139986407
159444692
691492120
724326876
983985927
251094712
152561009
792131553
180861803
476483174
1452228
679903340
114028487
708839985
423908505
225822973
429359448
9466736
953695488
436416903
959114047
240526165
107335806
650502161
12379757
287665382
933862912
942860083
738691718
558510649
620168516
371537007
274844711
623148417
279582293
987362057
750619478
186197732
357095598
510881447
902418796
243287464
953649351
907632058
476806125
809306967
727854177
819910132
570386867
764835833
611887244
344597387
450766425
910364770
102481782
629698035
29150148
481972277
936537085
268534591
260715348
381774984
585667530
382893261
911169542
112154533
591605136
331297130
100491182
385648892
208930227
526140546
279211346
405427972
660409007
590142802
459806696
53145206
920995631
55370100
134571581
17455543
718102493
932130447
378290476
443943739
995093088
495485152
166838447
677450369
536652390
299447163
413875878
347019456
790616835
401087365
674458174
497150249
968644420
690322565
565564606
336689170
724139080
360653894
628112727
266556459
361543452
715542368
22581278
757604923
680287997
707587713
332304198
438535261
952075388
745412180
703848887
837650340
459308007
610684730
891363197
491768253
491907451
106297538
197340770
384941569
613666305
272360123
13407166
641047668
364360432
807736927
592006070
966598965
44347710
297001668
91130250
453928066
130696256
648143058
369810179
818355666
398836281
431726865
434816929
386195447
317310737
879656451
16710523
150004207
966779489
346473494
816624433
294967633
738712368
165191279
932740439
370933034
975757626
236961399
736079562
538911105
874518851
408359149
280935697
678959359
63337639
608642312
439711550
580068091
544497410
681131805
160316375
650626331
473135226
709385910
341069284
760195433
106563170
576616564
364567500
944290748
528424042
430588344
540846210
263836283
175618650
659431817
746488924
827935282
341654863
267044856
661574236
425953047
792637913
532638073
937013739
97170809
729788362
864885154
677389819
560845225
671437239
988304838
731711683
329319843
970543538
207117735
513331711
631101665
386080719
965628750
414553119
686622263
603391297
35090899
591795569
503657757
315682512
812207122
870343017
724625662
680320257
425789744
572220253
442992212
811409721
941178748
910875574
195346430
207884393
144231495
931789091
918296104
645913111
383026164
493588048
529150358
249091776
433616311
468097315
466732062
75351789
75629548
854150962
657412329
608956068
693292100
538419965
611837476
876314539
729440537
40287104
446651055
310912157
786975696
267530977
406859033
837407835
417020921
414228696
310868138
42565226
635162894
809200603
558189742
336732077
381476611
455990621
183342185
847763479
515383876
7157762
309882092
188037174
323820302
778766126
446014513
222180326
291198844
525205292
773152066
19922872
332704620
954765709
732880594
732292657
717463332
577059540
863588376
985387204
20955627
779696948
101605698
956760786
858438683
381947019
455687510
886442612
355786746
236879096
763978364
961942883
597379837
186655831
633794739
280635550
417872200
554329192
778664166
644836652
248178237
869852747
403474191
201537691
868038071
458137704
229156332
375969839
249905636
700289212
633950140
404829981
728905555
524800125
953191987
300981196
918466604
873722997
33042029
769839628
969273717
241273423
699350178
513533439
445417978
898759769
259606422
696368033
132811090
685667314
510247036
399579612
525277752
396008817
631123613
547504886
273649398
228342238
677088120
733594106
8347982
697089325
633699075
341724384
505315284
262991617
578670894
950129482
444811366
201834523
966595432
625747103
352733007
565385748
754848586
877561129
783214301
514008719
19330296
382879419
425989767
156055561
62047703
875124909
166435034
667610294
506148191
704734229
858112488
955609796
892103293
619142141
233022283
39574922
294010421
865199719
10837708
575534670
373341068
406804104
371151498
104400576
689387959
99015139
482649250
412066532
122431568
814430619
950258660
340387203
215191320
189172628
323297379
298432973
987404995
718009330
641255710
832046280
772679815
268742253
959291639
772341194
468268894
402331008
114978564
373002998
265504991
857410640
892946128
485008139
38295697
563482825
981629778
361584944
694246558
547625273
434623452
623291877
173466935
553502090
374421001
678435927
88207624
168216150
10414290
467575491
68023300
104948447
605938093
350705381
618540835
653500165
174263023
314495585
155792468
248261589
896612360
797353133
7357558
343086950
466442634
112781074
216445658
930226613
692388020
306741097
52816672
77659822
447916747
374973221
504812283
311621438
421261459
906920377
932838846
812250294
119773167
180042014
358704105
860313646
244424723
374905828
568931215
895129562
595134292
890347893
903531011
677781709
677435502
403996068
648634383
519916322
180000274
910315549
94888456
317957290
841232222
927328243
690117653
585820157
45812586
383431596
273149487
670433334
637160948
663269563
941395007
137145947
970289344
561412654
481531983
570830165
218459241
167390767
6516905
946343865
975227964
169105717
80587501
764047266
371074737
718505296
989851021
784685580
864461055
743640900
10551882
121073150
357425244
356174794
158186246
117108448
454813143
505816428
583326358
392779819
561814548
314152546
637269009
214270702
816977490
106365792
28358718
102297397
572003003
182594221
127655298
920959275
921646213
343996900
869179795
357141021
745375538
954415805
847582103
277715566
647901926
126278410
126342910
930513753
194317062
246340807
972529356
310028266
23376597
115563823
12693442
467089621
241874287
481300179
536872880
484546500
191560044
314402385
394339415
416377811
23359505
964798112
151651728
316064758
640465994
970184557
641171241
833850005
748747661
346797219
922727205
619172730
107726945
890198423
960081541
808624165
757328061
745463309
983747216
242446019
629697865
172759569
798573302
474031456
564183478
846806955
711066166
88453623
934664561
718183810
407496521
848433925
928611384
931464960
743066380
876797051
740479962
359571524
444010839
868877717
908641759
563635614
813641217
28866304
565825300
300524904
639309253
479072412
941027315
909645976
84831929
550912744
546401459
93471017
345377379
25597804
381382292
498329021
916143472
857993636
303588150
833876386
859902763
996265439
536836366
877811962
471228127
860824583
207592736
218539897
750649924
447439478
2296211
964587218
365905077
135366568
880606065
160095868
66011934
512109427
37385841
27898881
729042498
418368306
451310640
828185443
491063651
817039132
889788736
23783254
640032218
455379502
125334049
499227628
176475909
508205846
896281055
13033770
984589580
18954772
625127140
328475000
913865847
234391266
481334211
11382858
142906464
564948326
754090685
826608819
960680750
70345597
721563238
186960342
905101675
101718006
995103967
837105922
260850176
942297303
407216947
557472188
270124774
928045528
478032182
45810417
989130178
319608779
186142936
97289407
8671571
100403811
878737857
691438099
340219994
426040683
394273947
656731625
146954264
725518305
655949033
879565073
431964922
800718422
257350272
312723757
931529132
39687596
594245392
255700711
676392348
669995747
318736046
729465597
500487419
283079347
544058602
510982859
170418708
452126747
359862058
662665655
575822711
86022257
773594359
157440548
296379268
748471944
373287242
618710819
297685640
252022114
554131197
764935285
456531106
456424351
221714272
224935183
740596979
133340017
976343577
353404720
789306920
874460090
66534015
426228691
402446023
604691163
332081023
589871123
757377973
688935024
799649886
35244497
548596308
230002146
511513566
806083829
432687310
733634243
35919150
668182074
946569105
475305710
596198828
555262582
227393506
170406845
19167683
276350267
573260353
784243442
304664565
842474149
739632386
62815971
497810015
903741312
335150689
513229315
181563933
668267208
429984610
815751405
263144614
164954573
187956886
334736785
910266303
957387219
72946819
718771935
223139545
58979326
359673535
472248578
90918138
215840917
741207441
794915755
328624622
401828885
82634640
250934172
77667953
669165240
792578055
141991721
67691925
535477363
844830612
503010158
833081475
128229264
302408585
441025879
608871869
399049643
632161789
484055214
677075466
575952844
884304427
587474130
914070094
995710794
803564676
768762095
37832564
254288850
402815005
387379761
31005955
771784918
357489355
866243966
734004286
305033022
998550137
513178639
101805066
462459584
235384032
227408548
9199909
361564272
373765461
594557473
466529221
639642702
249841497
983624070
549082533
937906732
334397336
337067721
836454484
614013513
20374905
180968804
60832795
159933456
295151378
51355142
723029807
461591728
857045999
401098870
431457458
246338184
805390399
963635150
428410982
733906717
714631324
319716133
288314471
859419872
58606586
367321634
103958737
347392578
850603850
437767487
176276443
257212668
162842648
83123836
717371477
796102138
15947448
585811415
871627472
434727756
312211744
662816194
406637281
113701571
957853412
20649584
330828679
300092493
162162250
997299144
141505483
739382704
133311212
792397571
920708829
717331455
476391339
155877602
216448948
684302078
880624864
720300387
501746630
152378265
533967442
165079537
90225823
237328252
678504508
274399127
51733473
675773559
275237775
216006844
400801341
791859198
706298737
12366818
591631745
666219759
689801224
891715268
800830285
905048817
563122822
962899626
713135881
971368130
998354300
883264878
849607798
528190252
54433753
15956685
157149584
565322207
252200878
462966258
824909097
442788849
301133463
287706626
199266427
245484410
227872717
784812355
429842346
232073485
533404430
441746648
102198130
764548879
23597508
983483265
529165057
617314869
450197046
798897796
546575476
412918581
338975430
107191356
864033874
953449823
282097419
522364651
266148968
299328051
874917430
816287709
595391314
673164386
260508440
383267822
356282428
660040316
455427441
513995972
923846002
445087035
439124660
71808991
524010012
568036485
329736689
381754056
268103103
643282270
66001229
804331902
277316215
186659101
162084288
270211155
396774604
979334310
781657885
932497942
722467942
338347397
823557719
857136151
376461938
918360802
589440910
557775564
865709576
56984489
129378867
379074601
551000841
140240640
788785129
734065109
166676826
829914829
788175716
605352132
708295812
532190083
929780381
689065473
576987094
108328282
979496629
694717993
160042716
843419277
979402763
150877114
420959625
485922261
40786407
747740870
29397719
201446995
723632428
4909118
560451092
44978909
364996427
228402249
406800485
653094484
42165645
666295259
289324858
800406317
738508533
790923193
736468825
31959169
245075895
168339365
555243500
46612499
754596748
716547019
4236547
303872861
978374392
827312797
299476687
158454460
423465627
367066388
847497312
397499443
175418007
159487631
503412682
361403332
539521219
883666455
76898712
904000485
573026537
608391809
191481229
428419009
207971456
92505094
417468162
801244165
876514787
127203440
56752605
359191681
864327850
808973263
649174810
14182944
787673965
459509117
951539479
689381869
918234867
984970955
435451124
626726185
141716484
585942368
682994563
42913965
430836931
220328311
655169889
926458361
872206853
541856621
380901634
905309239
282771030
458886623
478711743
422598561
605395941
912986417
448214648
10570046
872854959
886800300
279668904
66377855
362303489
359587471
153918714
232907792
653701310
260075288
593961496
968608234
39985973
714890347
667879849
46461814
938570466
48481897
109460208
441774804
573868458
795731126
433308348
474700756
948292537
415827500
766602376
457149440
887219451
614497206
716856736
207362781
373202750
77847380
514658381
811323987
9492299
637383089
820951798
787475567
846395242
68314033
2995550
723810093
339285722
669219482
181981636
862689018
900294601
573655610
458366168
316469001
519291281
611463419
45211092
451401187
491353352
859700487
397619265
875189167
25894363
363205944
293653025
343973985
573559317
438875166
709609532
40052336
492529666
533546518
492566763
467643555
823984366
387486109
611554972
313356941
431363803
564731480
177480697
728851185
323908715
53256141
226791387
759719623
405856524
412586451
832880999
53794016
726558154
744661215
704869380
702405093
784433315
867463677
113304069
767759889
855410036
314769352
337132677
93192047
490617955
928387354
648980932
615762405
984959470
904990032
462151531
422660957
944476906
527142328
985860050
452396479
953837203
760342302
649870710
531706038
94571237
8317595
781799208
654677126
242701692
489518647
793022042
868721450
674589605
625812556
433772015
764630855
790598723
853014525
29439828
267361308
81539331
385902353
942123994
295136393
319394248
254344043
784116933
94398800
315876376
22147759
138493841
784207545
605338166
373410967
220756049
872663651
445574146
878650114
881025253
442071223
842179769
145814406
963444269
987368258
142417656
29309225
755394812
569232242
744589998
93075110
553549222
2339527
948760724
265900235
639700406
666653443
744923733
656099059
227883733
206696641
709083606
719095653
515683810
122079250
979512761
497617995
711817126
888363217
142769642
600372087
70920227
689248800
962245815
151339612
384927851
746817458
316672201
192700142
30394239
176688750
88533999
961922217
526136129
532274047
876907005
535896421
217537756
135026920
720557008
774862860
299506360
147624342
819148277
918807968
175273830
184219433
857904872
23602638
290672706
653741549
114450346
361035613
670804504
320675435
535288503
867401777
431194369
583458539
815331554
455414873
394675135
74186381
66747103
686679278
464610525
776221827
275275724
322600043
187752089
71110135
853575573
788088828
311301544
673803967
599079022
669555091
776110136
543628173
548930837
512664974
790025259
666070283
203962474
348809752
28009974
130965036
64427630
3112162
714662052
630546941
488032693
107271517
776272724
669947630
80538331
175198121
416641355
202589985
314701577
917455102
212393523
536961165
499853159
290595405
476898874
231475902
957574952
384268883
653299557
385509075
596409032
620435856
921661458
725237561
472593073
203324932
434684363
855924149
695098788
988095755
201290125
305507973
74997278
602416883
807401253
167627527
364721386
27859975
169563135
433188283
133109760
91268167
972173536
26323578
953965225
407040703
464440385
120049587
99928305
940431738
309691296
325361805
494535177
172763822
226866831
466929037
878352645
150636076
889828576
367830146
831928405
865198636
914299402
916053195
726035637
972094113
313609976
599366507
472679110
727152739
383074132
914033438
863467722
794520834
823735693
417429163
232140240
26536890
76336256
958588455
740741275
542923822
604655573
512122005
554726583
831832285
207269112
479515060
611315048
659918269
789519915
908355843
772138993
335271100
831281177
837705106
762998892
913635054
563758803
715630938
725967144
22827332
649971033
129612586
200697991
294455735
267202696
255564429
475255181
280722677
748418846
920804218
36342451
896155013
352875037
135175135
153125942
12630753
701170787
612203327
452584430
919670523
632803983
246794908
276453927
508620203
711948495
369116740
763826793
972056529
849642553
273510
860986801
679776702
493122450
523189000
283897962
601363158
944710788
718811318
561139069
225661545
390269887
277807419
965014941
140617158
97784361
541408225
590373012
409175316
51557679
636703887
180411836
627519921
363210857
947709796
46923211
135940284
127957356
228332415
264266827
883511673
318190098
524921538
292468515
151034989
513360667
135837560
283157563
201072459
781270568
134785781
953040276
685624615
229443925
278047800
210177359
179454947
945555717
339000037
14885554
612554614
724709807
53115596
917110815
388668980
970605144
509899240
281819183
671647882
498702339
563479643
346035553
707187429
802967429
610232811
323333676
182949334
629363175
619449494
802630876
824788688
859624039
10713149
219661032
526403709
984036632
793517457
65543609
431273393
980613951
161202079
544293705
461959773
653289878
915590621
745482031
98468239
521469929
930292815
414394934
159363281
423501317
165123920
947886088
930234056
486020833
33551634
503538681
324763876
906845322
937611538
327033890
116542169
526945401
190722819
351970055
165976872
875582671
311419783
339833249
190067475
939373050
788089720
495337090
114551141
683939310
430886829
783135531
481744071
157556674
826983327
176012401
478159307
250201348
510175631
229900578
367463223
367446646
609448031
770523759
642346840
843418836
794471969
275990549
425016221
349199628
667078853
349969681
769102823
618814432
310367661
479215247
537689888
700543134
287045771
266293270
169588619
4675643
1336787
724124624
551214249
281871586
445637772
403894564
106734516
4144555
589871444
406496713
66077685
19850634
17248821
67305169
888883201
601969301
921902231
224584190
501833887
827322823
246404664
955860188
168113805
625908144
725783276
799725183
113326307
647155230
259369581
859538931
990833116
607396809
295354679
194788376
451277586
188813484
153704821
899973875
815639274
100200276
857494110
846620724
856244514
997390988
443933574
660064136
16527364
613081723
559408150
616995976
251940494
590088243
874395158
162309347
386062929
669439718
783197838
591441081
75714179
409493144
736132523
279459439
494264099
938536110
486861092
874290781
372368795
522776085
59792325
970155031
537829656
444937015
342260423
341732236
837119522
704777983
828548901
709372427
214225861
267857169
789076173
701274811
702014600
891393940
444531641
829270490
74319571
765966334
261708198
812131497
204961811
82387593
72392692
626283474
3213290
673263205
292663607
622329788
379895252
664441787
694552208
376883135
270430779
861940246
225978820
404341187
153185769
792919554
730484412
635888617
601564193
761083052
70061055
7875997
122178547
996477485
501933130
17833238
424483657
471718835
217041180
424784740
106024326
989710571
431091880
571236307
787428023
698947695
644017858
579959298
811530617
172955618
898521853
725961139
439354975
8950180
176974837
470242999
81542876
840696237
816575738
835654147
779148518
626358004
543363238
662666274
6597547
421114984
153804248
557186353
43378249
465202022
756471106
854066258
874543611
601586739
141351337
13406244
218346959
410137357
674865971
607555924
499892066
20180139
608778049
31988402
732318648
904647625
655945019
975728819
289768404
952392219
591996895
355952162
24238004
623080915
251696913
210566809
649471875
359455838
230144385
927227557
762207944
583366867
508946086
445954925
496217581
755837113
823173575
608267289
384081073
386901795
299997311
665161959
323911966
109665966
972545382
65747228
561398565
820700820
799240865
770462529
693627520
322130019
824106355
82121354
48365089
782949055
215630539
92662692
398262981
88000842
906361486
786803178
651435260
679635408
982529166
432357177
486592993
749245713
444147290
918516311
858415095
207922705
730363647
498862868
152063498
616768937
355046296
4325951
227848352
31457428
445697260
474209759
845994721
90878020
786814446
779013475
172319067
602044124
788669732
994270799
292212479
704302614
179496557
297959911
750534487
216020369
660605407
553743801
843519096
562732517
371055632
869089740
120532760
717704738
84452923
784307002
875561278
434187488
533534180
907494824
638142802
139857732
133101163
926394629
713219905
767481063
748530105
83767018
172459068
8520636
704673579
956106770
233303973
681163404
739148195
743767086
375973189
358942155
472129257
196976867
940507081
682457407
149061885
819526392
912236161
174812423
623385196
610459195
165021016
327876079
792828258
284832928
437362578
756589512
555617746
112377551
909271311
431116442
335790181
640801662
589741391
44092030
852008966
753712394
791928986
761162351
71195870
243707279
649061409
279466313
271303576
108463707
583032461
135112030
176109142
136973031
555388080
858719275
476892226
32851836
598303503
17449754
581226632
545721516
330623560
1863306
730421289
546539521
900794686
735626789
704161921
231695929
123158654
908026643
132128148
812428472
763495636
584036588
428496504
808939337
331809978
875154907
870843680
365512424
205053571
277328236
202540425
435308857
923720027
685683474
292480421
722583519
126818240
56755154
645733209
82828366
927572887
48708466
29659374
946385920
864587441
951523487
122351821
808825362
150132593
990164285
702746366
282936172
638403467
801455939
321211396
53215119
458534762
266409685
125269236
643503173
524890093
125779282
214980508
30571462
271768132
182215067
488186307
562068216
890307403
881761414
806790952
173349302
390259222
822813427
837472761
334261332
939256148
597743776
143693174
850793362
871312572
5901451
881760327
107385296
42280757
723432808
312478212
799491393
119077813
140486818
592615815
765382115
341683976
744461858
927338440
876445160
534405019
504823798
752101402
972989873
108841956
286028570
69210027
878189617
604272105
36922850
388557034
407880353
958532316
6939121
321023034
989081950
183704891
619284995
255520328
815004355
574600625
978702137
870966403
877027516
447836131
60745993
932341823
408366809
915649637
130268346
938447244
497104224
163567515
902394799
809016584
153695760
822799258
377015799
566611326
873769447
826287314
31529938
456054268
393868018
871691135
256430388
527635238
546588673
810943495
64796614
709747100
164469325
514802543
614026922
972028968
953994792
596664076
821825070
337066671
284844140
986744251
880149319
444110904
152073621
420285038
901913800
895749525
680564395
431084842
747382876
937135321
397296394
408586804
267378766
368637389
39445819
4903561
511328435
670737721
955691922
626563028
437053109
518580963
505488699
917024854
762803106
448943112
32732848
341517544
525513971
162166529
709211727
386663672
627262016
364416204
58564796
986656949
790452807
733625118
636805970
661515863
578811603
633034470
660649210
645742726
185878743
700280998
938335638
512755513
918667682
347245324
917310589
906923028
832177748
253216803
486644479
349085337
932911852
541508400
627859922
525257729
600739480
951318382
668717673
286685754
318425178
606804708
728814638
612532666
225176407
590741604
869453674
847291189
927953410
727836984
859152368
88551234
897786353
856346566
765632925
724245064
395911525
437480213
907122364
586449528
658581912
830532276
483045591
610278319
101873229
537029409
36455309
741812047
982273970
674654664
867392460
551574004
90519464
415168342
515115394
498923263
411027915
3446035
492813031
437653394
15091524
17623895
577536603
486920037
197571950
71747316
149739333
129554370
547266612
320209955
614105840
491575565
376720841
972306548
628688645
169598690
110298165
221177868
139719662
103417867
563991920
543585515
208428563
858993900
16916115
370892635
936734451
617050023
21071381
677798495
976088811
17481013
34187106
97301040
38296649
885728528
744228272
311701827
253256978
125912162
398759322
174628370
251518334
905113319
639154048
77428268
145995521
157027385
504481407
114658857
718609236
885906954
509732309
909364719
56687583
863596225
630385854
163663780
799336410
699736535
416538086
69178219
219157598
492167255
458780999
147178555
627576931
328036378
438066396
875848161
326775800
344242943
976766309
933567434
372995729
242267950
606294859
801943729
52363646
97634423
825865627
54457978
355810503
819174375
849383200
396753469
332495788
853784310
567304291
682074311
951941336
984524022
601387500
240624487
417460765
187839416
356904319
924296553
924838427
11701174
217001027
995344583
71716129
513544018
228253458
432492170
330144657
960992561
250583944
538650653
455654800
279606191
813716750
260540255
132986472
477418784
916663631
379700081
600139019
585048304
978794457
587799451
335231042
998241353
962330909
869982618
521991727
721454774
39947245
391019579
207289266
776734369
83945910
838235358
117034012
35925222
993089300
115866814
255991831
344076126
740814965
540639487
39126886
667773183
954850507
584635429
711311207
41895322
534691968
264992224
281558266
117198817
859540340
94452386
680972260
360666942
461719427
454780072
900497568
383240686
928273134
81796587
321778180
38134642
495288021
884466367
865784937
73887201
359128417
889480745
305458385
574670252
578275580
851794603
36380405
305208792
726384624
98114813
875451112
172274975
404253345
496285278
733972888
407663580
596078708
3677