fork download 
  1. MOD = 1000000007
  2. def mul(a, b):
  3. 	c = [[0, 0, 0], [0, 0, 0], [0, 0, 0]]
  4. 	for i in range(0, 3):
  5. 		for j in range(0, 3):
  6. 			for k in range(0, 3):
  7. 				c[i][j] = (c[i][j] + a[i][k]*b[k][j])%MOD
  8. 	for i in range(0, 3):
  9. 		for j in range(0, 3):
  10. 			c[i][j] = c[i][j] % MOD
  11. 	return c
  12. def pow_mod(n):
  13. 	d = [ [1, 1, 1],[1, 0, 0],[0, 0, 1]]
  14. 	ans = [[1, 0, 0], [0, 1, 0], [0, 0, 1]]
  15. 	while n:
  16. 		if n&1:
  17. 			ans = mul(ans, d)
  18. 		d = mul(d, d)
  19. 		n >>= 1
  20. 	return ans
  21.  
  22. def solve(n):
  23. 	print n, " : ",
  24. 	ans = 0
  25. 	if n < 2:
  26. 		print 1
  27. 	else:
  28. 		ans = pow_mod(n - 1)
  29. 		res = ans[0][0] + ans[0][1] + ans[0][2]
  30. 		print res % MOD
  31. #test for 1 to 100
  32. def main():
  33. 	for i in range(0, 100):
  34. 		solve(i)
  35. main()
  36. #1 1 3 5 9
  37. """
  38. #brute force
  39. def main():
  40. 	s = [1, 1]
  41. 	for i in range(2, 100):
  42. 		s.append(s[i-1] + s[i-2] + 1)
  43.  
  44. 	for i in range(0, 100):
  45. 		print i, " : ", s[i] % (10**9 + 7)
  46.  
  47. main()
  48. """
Success #stdin #stdout 0.03s 7852KB
comments (?)
stdin 
Standard input is empty
stdout 
0  :  1
1  :  1
2  :  3
3  :  5
4  :  9
5  :  15
6  :  25
7  :  41
8  :  67
9  :  109
10  :  177
11  :  287
12  :  465
13  :  753
14  :  1219
15  :  1973
16  :  3193
17  :  5167
18  :  8361
19  :  13529
20  :  21891
21  :  35421
22  :  57313
23  :  92735
24  :  150049
25  :  242785
26  :  392835
27  :  635621
28  :  1028457
29  :  1664079
30  :  2692537
31  :  4356617
32  :  7049155
33  :  11405773
34  :  18454929
35  :  29860703
36  :  48315633
37  :  78176337
38  :  126491971
39  :  204668309
40  :  331160281
41  :  535828591
42  :  866988873
43  :  402817458
44  :  269806325
45  :  672623784
46  :  942430110
47  :  615053888
48  :  557483992
49  :  172537874
50  :  730021867
51  :  902559742
52  :  632581603
53  :  535141339
54  :  167722936
55  :  702864276
56  :  870587213
57  :  573451483
58  :  444038690
59  :  17490167
60  :  461528858
61  :  479019026
62  :  940547885
63  :  419566905
64  :  360114784
65  :  779681690
66  :  139796468
67  :  919478159
68  :  59274621
69  :  978752781
70  :  38027396
71  :  16780171
72  :  54807568
73  :  71587740
74  :  126395309
75  :  197983050
76  :  324378360
77  :  522361411
78  :  846739772
79  :  369101177
80  :  215840943
81  :  584942121
82  :  800783065
83  :  385725180
84  :  186508239
85  :  572233420
86  :  758741660
87  :  330975074
88  :  89716728
89  :  420691803
90  :  510408532
91  :  931100336
92  :  441508862
93  :  372609192
94  :  814118055
95  :  186727241
96  :  845290
97  :  187572532
98  :  188417823
99  :  375990356
https://ideone.com/kOYLeZ
language:
Python (cpython 2.7.16)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!