eolymp
Змагання

Комбинаторика. Формула

Трикутна павутина

Перед Вами нескінченна трикутна сітка. Вона влаштована таким чином, що якщо підпалити яку-небудь вершину, то ця вершина запалюється, у наступну секунду запалюються усі вершини, сусідні безпосередньо з заданою, далі усі вершини, сусідні з тими, що вже горять, і т.д. Вважайте, що вогонь ніколи не потухне.

Спочатку підпалена одна вершина. Потрібно знайти кількість вершин, що горять, через n секунд.

prb4368

Вхідні дані

Одне число n (0n109).

Вихідні дані

Вивести кількість вершин, що горять через n секунд.

Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB
Вхідні дані #1
1
Вихідні дані #1
7
Вхідні дані #2
1500
Вихідні дані #2
6754501
Автор Андрій Селіванов
Джерело "П`ятірка за тиждень" 05 2013-2014