Log inSign up
Problems / B091

Filling the measure

200 ptsCases 15Set by dongbinna
Added October 30.
1 solved1 attempted1 submissionssolvers took 1.0 tries on average

Statement

Someone writing out a score has to fill a measure with notes and leave no gaps. The measure to fill right now is N beats long.

Only two notes can be used. One is a short note that takes 1 beat, and the other is a long note that takes 2 beats. The notes are laid out one after another from the left end of the measure, and the end of the last note has to meet the right end of the measure exactly. A different order of the notes laid out counts as a different measure.

So, given the length of the measure N, write a program that finds the number of ways to fill the measure. The answer can grow very large, so print the remainder of the number of ways divided by 15,746.

For example, suppose a measure N=4 beats long is being filled. Writing a short note as 1 and a long note as 2, the ways to fill it are as in the table below.

WayNotes laid out from the left
11, 1, 1, 1
21, 1, 2
31, 2, 1
42, 1, 1
52, 2

So when N=4 the answer is 5.

Counting the same way for measures from 1 beat up to 6 beats gives the following.

N123456
Number of ways to fill it1235813

Thinking about the note that sits at the far right of the measure shows the pattern. If the note at the far right is a short note, then N-1 beats were filled to its left, and if it is a long note, then N-2 beats were filled to its left. The two cases do not overlap, so the number of ways to fill N beats is the number of ways to fill N-1 beats added to the number of ways to fill N-2 beats.

As the measure gets longer the number of ways grows very fast. So do not finish the whole count and take the remainder at the end, keep only the remainder divided by 15,746 at every step of the addition.

Input and Output Examples

Example 1

Input

4

Output

5

Example 2

Input

5

Output

8

Example 3

Input

1000000

Output

7871

Input

  • First the length of the measure to fill N is given as a natural number on one line. (N is a natural number from 1 to 1,000,000.) N counts beats, so it is never given as 0, as a negative number or as a decimal. The input ends with this one line, and no other line is given.

Output

  • Print the remainder of the number of ways to fill the measure divided by 15,746 on one line. Only one number is printed, so no space is left at the end of the line.

Requirements

  • There are only two notes, the one-beat note and the two-beat note
  • A different order of the notes laid out counts as a different way
  • No gap may be left in the measure, and the notes may not run past it
  • If N is 1 there is only the one short note, so the answer is 1, and if N is 2 the answer is 2
  • Carry the remainder divided by 15,746 at every step of the addition so the numbers do not overflow
  • You must write a program that reads from standard input and writes to standard output
  • Trailing spaces at the end of a line and blank lines at the end of the output are ignored when grading
  • The languages you can use are Python and JavaScript
  • The memory limit is 256MB. The browser does not measure it, it only states it
  • The time limit is set by measuring the setter's reference solution on the same runtime
  • On this problem you submit code, not a prompt. That code runs in the browser on this device, and all that goes to the server is a fingerprint of the output and the time it took. Whether it is correct is decided by the server. The run time is a number each device reports, so the code and the device details are posted next to it on the leaderboard.
  • The output has to match the expected value down to the character. A space inside a line counts the same as any other character.
  • There are 15 cases, and 3 of them show the input together with the expected output. The rest are used only when you submit and are not shown on this page.
  • You have to pass all 15 cases to solve this.
Read the requirements carefully before solving. Tampering with the grading to make a submission look like a pass can get you sanctioned if caught. The code you submit is published on the leaderboard along with the result.

Examples

3 public cases. Judging also uses hidden cases. You have to pass all 15 cases to solve this.

Input
Expected output
4
5
5
8
1000000
7871

Solution

Your code runs on this device. Only the fingerprint of the output and the elapsed time go to the server. The server decides whether it is correct.

0 chars1 lineMemory 256MB (recorded only)Reference 20ms

Submitting requires you to log in. Running against the public cases works without one.

You can test with 3 public cases. Submitting runs the hidden cases too.

People who solved this problem

The time shown is the time spent solving. Input reading time is outside the solver's control, so it is excluded. And since each device reports this value itself, we record which device measured it.

1bampal2776ms119 charsPythonWindows NT 10.0 / Chrome/156.0.0.0 / 8코어 / 16GB

Log in and you can see the code once you solve this problem.