Jason's Theorem

View as PDF
Submit solution
Points: 10 (partial)
Time limit: 0.5s
Memory limit: 64M
Author:
kobortor
Problem type

Baba Jason was playing around with his slide rules one morning and discovered an important mathematical property:

\displaystyle \text{If }x=x_{x}^{x} \text{ then } x=x_{x_{x}^{x}}^{x_{x}^{x}}

Jason brought the discovery to Nathan, his math professor. Nathan was so impressed by the discovery that he convinced Jason to co-publish it in arXiv. Before Jason could publish the paper, Nathan informs him that mathematicians are very skeptical people, and will want to see more iterations in the sequence before they accept it.

The sequence is written in a markdown language known as \LaTeX, and the sequences are as such:

(0) x=x
(1) x=x_{x}^{x}
(2) x=x_{x_{x}^{x}}^{x_{x}^{x}}
(3) x=x_{x_{x_{x}^{x}}^{x_{x}^{x}}}^{x_{x_{x}^{x}}^{x_{x}^{x}}}
(4) x=x_{x_{x_{x_{x}^{x}}^{x_{x}^{x}}}^{x_{x_{x}^{x}}^{x_{x}^{x}}}}^{x_{x_{x_{x}^{x}}^{x_{x}^{x}}}^{x_{x_{x}^{x}}^{x_{x}^{x}}}}
.
.

Jason quickly realizes that this will take a really long time to type, so he asks you how many keystrokes it will take to complete the N^\text{th} iteration. Please help him!

Input Specification

A single integer N.

Output Specification

Print the number of keystrokes Jason needs to type modulo 10^9+7.

Constraints

0 \le N \le 2^{63}-1

Sample Input 1

0

Sample Output 1

3

Sample Input 2

1

Sample Output 2

11

Sample Input 3

2

Sample Output 3

27

Sample Input 4

3

Sample Output 4

59

Sample Input 5

4

Sample Output 5

123

Sample Explanations

The examples are given in the problem description.

Comments


  • 2
    htoshiro  commented on April 9, 2024, 7:55 p.m. ← edited

    python users: 😊 ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀ java users: 💀


    • 0
      Vastaway  commented on April 17, 2024, 4:00 p.m.

      thank you python 🙏