Problem Statement
For example, let G1 be a graph on vertices {0,1,2} that contains the edges 0->1 and 1->2. For this graph we have p(G1)=3: there is a path from 0 to 1, a path from 1 to 2, and a path from 0 to 2. Similarly, let G2 contain the edges 0->1 and 2->1. Then p(G2)=2: the only two valid paths are from 0 to 1 and from 2 to 1.
You are given an undirected tree T with N vertices. The vertices are numbered 0 through N-1. The exact format in which T is given is specified below.
We can change T into a directed graph U by replacing each undirected edge of T by one of the two possible directed edges. As there are exactly N-1 edges in T, there are exactly 2^(N-1) possible graphs U we can produce.
For each possible U compute the value p(U). Let X be the sum of those 2^(N-1) values. Compute and return the value (X modulo 1,000,000,007).
You are given the
A[0] = A0 for i = 1 .. N-2: A[i] = (B * A[i-1] + C) % MOD for i = 1 .. N-1: j = A[i-1] % i add an edge between vertices i and j
Definition
- Class:
- TreeWalker
- Method:
- calc
- Parameters:
- int, int, int, int, int
- Returns:
- int
- Method signature:
- int calc(int N, int A0, int B, int C, int MOD)
- (be sure your method is public)
Constraints
- N will be between 2 and 100,000, inclusive.
- A0, B and C will be between 0 and 1,000,000,000, inclusive.
- MOD will be between 1 and 1,000,000,000, inclusive.
Examples
4
0
1
1
1000
Returns: 34
The graph T generated by our pseudocode is the path 0 - 1 - 2 - 3. There are 2^3 = 8 possible ways to assign directions to these edges: In two cases (0 -> 1 -> 2 -> 3, 0 <- 1 <- 2 <- 3) we have p(U) = 6. In four cases (0 -> 1 -> 2 <- 3, 0 -> 1 <- 2 <- 3, 0 <- 1 -> 2 -> 3, 0 <- 1 <- 2 -> 3) we have p(U) = 4. In two cases (0 -> 1 <- 2 -> 3, 0 <- 1 -> 2 <- 3) we have p(U) = 3. The sum of p(U) over all possible U is X = 6+6+4+4+4+4+3+3 = 34.
10
0
0
0
1
Returns: 13824
16
15
1
1
16
Returns: 917506
1000
385498676
349131547
115776323
614879544
Returns: 245566366
100000
111222333
444555666
777888999
123456789
Returns: 119729770
2
1
1
1
1
Returns: 2
3
1
1
1
1
Returns: 10
4
1
1
1
1
Returns: 36
99998
1
1
1
1
Returns: 262644693
99999
1
1
1
1
Returns: 993270774
100000
1
1
1
1
Returns: 74435183
99998
0
1
1
10000000
Returns: 480170138
99999
0
1
1
114514
Returns: 264202027
100000
0
1
1
13131313
Returns: 136127565
46799
0
1
1
20000
Returns: 993821221
100000
0
1
1
50000
Returns: 830403780
16809
282475249
622650072
984943658
144108931
Returns: 986971397
15976
101027544
457850877
458777922
7237710
Returns: 272195185
72677
115438164
784484491
74243042
114807988
Returns: 731146625
33880
441282326
16531729
823378840
143542613
Returns: 972551115
53270
474833168
264817708
998097156
817129561
Returns: 254099312
82250
197493099
404280277
893351816
505795336
Returns: 87541322
18648
636807825
563613512
101929267
580723811
Returns: 943562390
84683
358580978
624379148
128236577
784558822
Returns: 2053357
17274
110010670
551901392
617819335
399125486
Returns: 255542147
93307
356425227
899894090
585640194
937186358
Returns: 669471771
51463
25921152
510616708
590357944
771515669
Returns: 45973624
75067
44788123
927702195
952509529
130060904
Returns: 2626142
47151
83454665
108728548
685118024
118797802
Returns: 669103456
17463
571540977
194847408
35308226
158374934
Returns: 581156430
71052
824938981
595028635
962408012
137623866
Returns: 793155136
99789
20739061
107554536
635339424
654001670
Returns: 11125974
41894
269220094
34075629
478446500
864546518
Returns: 117341551
47716
581030104
557810403
146319449
908194299
Returns: 406877037
87197
657821123
753799505
102246881
269406753
Returns: 559178143
49735
884936716
807130336
578354438
892053145
Returns: 922469798
63041
4844896
616783871
382955828
330111138
Returns: 568938047
31636
723153176
70982397
147722293
70477905
Returns: 520299165
42127
606946230
190959744
912844174
341853636
Returns: 356006449
84382
343098142
456880399
534827967
280090413
Returns: 34887408
2216
589673557
6441594
889688008
57716396
Returns: 808467632
41213
14119111
515204530
388471006
681910963
Returns: 164985744
16992
400285364
322842082
463179851
828530768
Returns: 145584849
42149
73185694
316824712
260973670
815859902
Returns: 63798845
61264
51724829
194314737
318153057
111631617
Returns: 383911899
28570
304555640
213110678
541437335
49077007
Returns: 625801820
7939
63936096
270649095
428975319
685583455
Returns: 561403259
58738
272112289
398556759
334948904
724586127
Returns: 139637634
41447
23129505
836045813
436476770
60935239
Returns: 237559802
48459
915896220
304987844
34712364
881140535
Returns: 991797669
28045
901915393
197941363
348318738
152607845
Returns: 431663669
67437
543436550
290145159
681808622
977764948
Returns: 842223666
4893
971307217
737195271
755537
399399248
Returns: 742952623
47009
459413495
951894884
537140623
848682421
Returns: 486964065
38266
86531967
289335734
755699914
623161626
Returns: 421625563
73462
43046040
358796010
943454679
771024153
Returns: 636120512
100000
16807
282475249
622650072
984943659
Returns: 64912049
100000
144108929
470211272
101027544
457850879
Returns: 284764826
100000
458777922
7237707
823564440
115438166
Returns: 603090464
100000
784484491
74243042
114807987
137522504
Returns: 963993369
100000
441282326
16531729
823378840
143542613
Returns: 933138993
100000
896544303
474833168
264817708
998097158
Returns: 854619919
100000
817129559
131570932
197493099
404280279
Returns: 546147458
100000
893351816
505795334
954899096
636807827
Returns: 854866171
100000
563613512
101929267
580723809
704877634
Returns: 576625208
100000
358580978
624379148
128236577
784558822
Returns: 174697494
3
0
0
0
1
Returns: 10
100000
0
0
0
1000
Returns: 74435183
100000
0
0
0
1
Returns: 74435183